How to Compute the Volume?
Santosh Vempala
MIT
February 25, 2005
11 a.m. - 12 noon
Fuller Labs 320
Abstract
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.)
Biography
Santosh Vempala is an associate professor in the Applied Mathematics Department at MIT. His research interests are in algorithms, geometry and randomness. He has been at MIT since he graduated from Carnegie Mellon in 1997, except for the year 1998-1999, when he was a Miller fellow at UC Berkeley. Every couple of years, he teaches a course called "An Eye for Elegance". He recently completed a book titled "The Random Projection Method" (Amer. Math. Soc. 2004). He lives in Somerville MA, with his partner, Rosa, who is an assistant professor of psychology at Southern New Hampshire University. More information can be found on his Web site.
Host
Neil T. Heffernan
Refreshments will be served.
Last modified: September 25, 2006 14:07:01