Massachusetts Institute of Technology

April 12, 4:15pm




Computing the volume of a geometric body is an ancient, basic and surprisingly difficult task. Even for convex bodies in n -dimensional space, no polynomial-time deterministic algorithm can approximate the volume to within a factor that is exponential in n . On the other hand, Dyer, Frieze and Kannan showed that, using randomness, the volume can be approximated to arbitrary accuracy in polynomial time (the 23rd power of n ). This remarkable result has been improved several times; each improvement has yielded new techniques for algorithm design and has contributed to classical fields such as geometry and probability. In this talk, we will discuss the history of the volume problem, illustrate its difficulty and describe the latest algorithm whose complexity grows as the 4th power of n . The key ingredients of the algorithm are: (1) a method for rapidly “morphing” one convex body into another and (2) a geometric random walk that “mixes” rapidly from any starting point inside a convex body (the only walk known to have this property).

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

Return to Applied Math Colloquium home page