Dispersion of Mass and the Complexity of Randomized Algorithms

COMPUTER SCIENCE/DISCRETE MATH I
Topic:	Dispersion of Mass and the Complexity of Randomized Algorithms
Speaker:	Santosh Vempala
Affiliation:	MIT
Date:	Monday, January 23
Time/Room:	11:15am - 12:15pm/S-101

---

Perhaps the most appealing conjectures in asymptotic convex geometry are (i) slicing (or isotropic constant) and (ii) variance. Together, they imply that for a random point X from an isotropic convex body in \R^n, the variance of |X|^2 is O(n). We prove a reverse inequality: for any isotropic convex polytope with at most poly(n) facets, the variance of |X|^2 is AT LEAST n/ln n (up to a constant). In fact, the lower bound holds for any polytope of unit volume with poly(n) facets contained in the ball of radius poly(n). It implies that in order for most of such a convex polytope to be contained between two concentric spheres, their radii have to differ by about 1/\sqrt{ln n}; in contrast, most of a unit-volume ball lies in between two spheres whose radii differ by only about 1/\sqrt{n}. This geometric dispersion leads to linear and quadratic lower bounds on the randomized complexity of some basic algorithmic problems.

This is joint work with Luis Rademacher.