Dispersion of Mass and the Complexity of Randomized Geometric Algorithms

Simple item page
dc.creatorRademacher, Luis
dc.creatorVempala, Santosh
dc.date2006-08-12
dc.date2008-06-17
dc.date.accessioned2026-07-07T09:44:52Z
dc.date.available2026-07-07T09:44:52Z
dc.descriptionHow 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.
dc.descriptionFull version of L. Rademacher, S. Vempala: Dispersion of Mass and the Complexity of Randomized Geometric Algorithms. Proc. 47th IEEE Annual Symp. on Found. of Comp. Sci. (2006). A version of it to appear in Advances in Mathematics
dc.identifierhttps://arxiv.org/abs/cs/0608054
dc.identifierhttp://arxiv.org/abs/cs/0608054
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/163023
dc.subjectComputational Complexity
dc.subjectComputational Geometry
dc.subjectData Structures and Algorithms
dc.subjectFunctional Analysis
dc.titleDispersion of Mass and the Complexity of Randomized Geometric Algorithms
dc.typetext

Files

Collections

arXiv