# Gaussian Cooling and O*(n^3) Algorithms for Volume and Gaussian Volume

arXiv: https://arxiv.org/abs/1409.6011 · HTML: https://mlsanity.com/paper/1409.6011/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Sep 2014.

## Built on by (most cited first, 5 of 5)

- [Faster logconcave sampling from a cold start in high dimension](https://mlsanity.com/paper/2505.01937/) (2025)
- [Efficient computation of the volume of a polytope in high-dimensions using Piecewise Deterministic Markov Processes](https://mlsanity.com/paper/2202.09129/) (2022)
- [Approximate Integer Solution Counts over Linear Arithmetic Constraints](https://mlsanity.com/paper/2312.08776/) (2023)
- [Truncated Log-concave Sampling with Reflective Hamiltonian Monte Carlo](https://mlsanity.com/paper/2102.13068/) (2021)
- [Thin-shell stability of Gaussian cooling: logconcave sampling with sesteric complexity from a cold start](https://mlsanity.com/paper/2609.15884/) (2026)

## Abstract (arXiv)

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^*(maxn3, σ2n2) for the first sample and O^*(maxn2, σ2n2) for every subsequent sample.