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