Dispersion of Mass and the Complexity of Randomized Algorithms

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$ and is 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.

Joint work with Santosh Vemapala.