# A Cubic Algorithm for Computing Gaussian Volume

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2013.

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

- [Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling](https://mlsanity.com/paper/2109.13055/) (2021)
- [Faster logconcave sampling from a cold start in high dimension](https://mlsanity.com/paper/2505.01937/) (2025)
- [Fast Mixing of Data Augmentation Algorithms: Bayesian Probit, Logit, and Lasso Regression](https://mlsanity.com/paper/2412.07999/) (2024)
- [Data-Driven Chance Constrained AC-OPF using Hybrid Sparse Gaussian Processes](https://mlsanity.com/paper/2208.14814/) (2022)
- [Latent-IMH: Efficient Bayesian Inference for Inverse Problems with Approximate Operators](https://mlsanity.com/paper/2601.20888/) (2026)
- [Truncated Log-concave Sampling with Reflective Hamiltonian Monte Carlo](https://mlsanity.com/paper/2102.13068/) (2021)

## Abstract (arXiv)

We present randomized algorithms for sampling the standard Gaussian distribution restricted to a convex set and for estimating the Gaussian measure of a convex set, in the general membership oracle model. The complexity of integration is O^*(n3) while the complexity of sampling is O^*(n3) for the first sample and O^*(n2) for every subsequent sample. These bounds improve on the corresponding state-of-the-art by a factor of n. Our improvement comes from several aspects: better isoperimetry, smoother annealing, avoiding transformation to isotropic position and the use of the "speedy walk" in the analysis.