Seminar: October 24
Nisheeth Vishnoy, Microsoft Research India
Approximating Fundamental Functions and their Applications
Note non-standard day
I will talk about approximations to real functions such as exp(-x), 1/x, and x^k. One can combine such approximations with powerful tools from linear algebra
such as the Spielman-Teng solver and Conjugate-Gradient type methods to obtain primitives crucial to designing fast algorithms for problems such as simulating
random walks, graph partitioning and semi-definite programming. Such approximations may be useful not only in the context of algorithms, but also for
proving lower bounds.