2014/09/21 by Ben Cousins, Santosh Vempala, Cousins, Ben +1 · 1 citation
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Markov Chains and Monte Carlo Methods #Point processes and geometric inequalities #cs.CC #cs.DS #math.FA
paper · pdf · doi:10.48550/arxiv.1409.6011
This paper is a combination of two previously published conference papers: "A Cubic Algorithm for Computing Gaussian Volume" (SODA 2014, arXiv:1306.5829) and "Bypassing KLS: Gaussian Cooling and an $O^*(n^3)$ Volume Algorithm" (STOC 2015). Additionally, this version has a major simplification to the main proof in the latter conference paper. (Lemma 3.2 in this version) 36 pages
openalex publication_date 2014/09/21 · arxiv created 2016/12/05 · arxiv updated 2016/12/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present an O^*(n3) randomized algorithm for estimating the volume of a well-rounded convex body given by a membership oracle, improving on the previous best complexity of O^*(n4). The new algorithmic ingredient is an accelerated cooling schedule where the rate of cooling increases with the temperature. Previously, the known approach for potentially achieving this asymptotic complexity relied on a positive resolution of the KLS hyperplane conjecture, a central open problem in convex geometry. We also obtain an O^*(n3) randomized algorithm for integrating a standard Gaussian distribution over an arbitrary convex set containing the unit ball. Both the volume and Gaussian volume algorithms use an improved algorithm for sampling a Gaussian distribution restricted to a convex body. In this latter setting, as we show, the KLS conjecture holds and for a spherical Gaussian distribution with variance σ2, the sampling complexity is O^*(max\n3, σ2n2\) for the first sample and O^*(max\n2, σ2n2\) for every subsequent sample.