Monday November 17, 2003

Speaker: Santosh Vempala (MIT)

Title: How to compute the volume?

Abstract: Computing the volume of a geometric body is an ancient, basic and surprisingly difficult mathematical task. Even for a convex body in n-dimensional space (given by a membership oracle), no deterministic algorithm can approximate the volume to within a factor that is exponential in n. On the other hand, as shown by Dyer, Frieze and Kannan, using randomness, the problem can be solved in polynomial time, leading to many developments in the fields of Markov chains and geometric inequalities. The complexity of the latest algorithm for the problem grows as the 4-th power of n. The key ingredients of the algorithm are (1) a method for "morphing" one convex body into another and (2) a geometric random walk that "mixes" rapidly from any starting point. Time permitting, we will also discuss applications to optimization.

This is joint work with L. Lovasz (Microsoft Research).