Name
Abstract | ||
|---|---|---|
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 \mathbb{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. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.aim.2008.06.004 | Electronic Colloquium on Computational Complexity |
Keywords | DocType | Volume |
lower bounds,variance hypothesis,dispersion of mass,randomized algorithms,determinant computation,volume computation,property testing,convex body,convex geometry,lower bound,randomized algorithm | Journal | 219 |
Issue | ISSN | ISBN |
3 | Advances in Mathematics | 0-7695-2720-5 |
Citations | PageRank | References |
5 | 0.67 | 15 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luis Rademacher | 1 | 269 | 21.60 |
| Santosh Vempala | 2 | 3546 | 523.21 |