Theory Group

Department of Computer Science The University of Chicago

Home Faculty Current Students Former Students Awards Join Us Other Theory Groups in Chicago Miscellaneous

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.