# 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.