Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm

We present an O*(n 3 ) 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*(n 4 ). 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 such complexity relied on a positive resolution of the KLS hyperplane conjecture, a central open problem in convex geometry.

Authors

• Benjamin Cousins
• Santosh S. Vempala

Keywords

No keywords are indexed for this paper.