Title: Approximation Theory and the Design of Fast Algorithms
Speaker: Nisheeth Vishnoi (Microsoft Research, Bangalore)
Date: 17 January 2014
Time: 2 – 3 pm
Venue: LH-1, Mathematics Department

I will talk about techniques to approximate real functions such as $x^s,$ $x^{-1}$ and $e^{-x}$ by simpler functions and how these results can be used in the design of fast algorithms. The key lies in the fact that such approximations imply faster ways to approximate primitives such as $A^sv,$ $A^{-1}v$ and $\exp({-A})v$, and in the computation of matrix eigenvalues and eigenvectors. Indeed, many fast algorithms reduce to the computation of such primitives, which have proved useful for speeding up several fundamental computations, such as random walk simulation, graph partitioning, solving linear systems of equations, and combinatorial approaches for solving semi-definite programs.


Contact: +91 (80) 2293 2711, +91 (80) 2293 2265
E-mail: chairman.math[at]iisc[dot]ac[dot]in