Dispersion of Mass and the Complexity of Geometric Problems

Luis Rademacher (MIT CSAIL)

How much can randomness help computation? Motivated by this general question and by volume computation, one of the few instances where randomness provably 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^n (the current best algorithm has complexity roughly n^4, conjectured to be n^3). 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. We also consider the problem of computing the centroid of a convex body in R^n. We prove that if the body is a polytope given as an intersection of half-spaces, then computing the centroid exactly is #P-hard, even for order polytopes, a special case of 0-1 polytopes. We also prove that if the body is given by a membership oracle, then for any deterministic algorithm that makes a polynomial number of queries there exists a body satisfying a roundedness condition such that the output of the algorithm is outside a ball of radius sigma/100 around the centroid, where sigma^2 is the minimum eigenvalue of the inertia matrix of the body.

Ph.D. Thesis Defense.

(The Algorithms and Complexity Seminar series talks are usually held Thursdays from 4-5:15pm in 32-G575.)