Dispersion of Mass and the Complexity of Randomized Geometric Algorithms
<|reference_start|>Dispersion of Mass and the Complexity of Randomized Geometric 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, 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.<|reference_end|>
@article{rademacher2006dispersion,
    title={Dispersion of Mass and the Complexity of Randomized Geometric Algorithms},
    author={Luis Rademacher, Santosh Vempala},
    journal={arXiv preprint arXiv:cs/0608054},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0608054},
    primaryClass={cs.CC cs.CG cs.DS math.FA}
}