Abstract of a paper by Luis Rademacher, Santosh Vempala
This is an announcement for the paper "Dispersion of mass and the complexity of randomized geometric algorithms" by Luis Rademacher, Santosh Vempala. 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 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. Archive classification: Computational Complexity; Computational Geometry; Data Structures; Functional Analysis The paper may be downloaded from the archive by web browser from URL http://arXiv.org/abs/cs.CC/0608054 or by email in unzipped form by transmitting an empty message with subject line uget 0608054 or in gzipped form by using subject line get 0608054 to: cs@arXiv.org.
participants (1)
-
Dale Alspach