Dispersion of Mass and the Complexity of Randomized Algorithms

June 20, 2006
Santosh Vempala | Massachusetts Institute of Technology and Microsoft Research

How much can randomness help computation? Motivated by this general question and by volume computation, one of the few instances where randomness probably helps, we analyze a notion of dispersion and connect it to asymptotic convex geometry. We obtain a nearly quadratic lower bound on the complexity of randomized volume algorithms for convex bodies in Rⁿ (the current best algorithm has complexity roughly n⁴ and is conjectured to be n³). Our main tools, dispersion of random determinants and dispersion of the length of a random point from a convex body, are of independent interest and applicable more generally; in particular, the latter is closely related to the variance hypothesis from convex geometry. This geometric dispersion also leads to lower bounds for matrix problems and property testing.

This is joint work with Luis Rademacher.

Speaker Details

Santosh Vempala is an associate professor in the mathematics department at MIT. His research interests are in algorithms, geometry and randomness. Every couple of years, he teaches a course called “An Eye for Elegance”. His book titled “The Random Projection Method” was published in 2004 by the AMS. He was a Sloan fellow during the period 2002-04 and is a Guggenheim fellow in 2005-06. He is a Visiting Researcher in the Theory group from April -June, 2006.More information can be found on his webpage: http://math.mit.edu/~vempala.