# Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Aug 2020.

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

- [In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies](https://mlsanity.com/paper/2405.01425/) (2024)
- [Sampling and Integration of Logconcave Functions by Algorithmic Diffusion](https://mlsanity.com/paper/2411.13462/) (2024)
- [Covariance estimation using Markov chain Monte Carlo](https://mlsanity.com/paper/2410.17147/) (2024)
- [Beyond the d2.5-mixing bound for Dikin walks on polytopes](https://mlsanity.com/paper/2607.13943/) (2026)
- [A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model](https://mlsanity.com/paper/2609.30215/) (2026)
- [The Geometry of Efficient Nonconvex Sampling](https://mlsanity.com/paper/2603.25622/) (2026)
- [Tight Bounds for Learning Polyhedra with a Margin](https://mlsanity.com/paper/2604.14614/) (2026)
- [On two proofs of d2 mixing of weighted Dikin walks](https://mlsanity.com/paper/2608.28566/) (2026)
- [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 show that the volume of a convex body in ℝn in the general membership oracle model can be computed to within relative error varepsilon using widetildeO(n3.5psi2 + n3/varepsilon2) oracle queries, where psi is the KLS constant. With the current bound of psi=widetildeO(1), this gives an widetildeO(n3.5 + n3/varepsilon2) algorithm, improving on the Lov'asz-Vempala widetildeO(n4/varepsilon2) algorithm from 2003. The main new ingredient is an widetildeO(n3psi2) algorithm for isotropic transformation of a well-rounded convex body; we apply this iteratively to isotropicize a general convex body. Following this, we can apply the widetildeO(n3/varepsilon2) volume algorithm of Cousins and Vempala for well-rounded convex bodies. We also give an efficient implementation of the new algorithm for convex polytopes defined by m inequalities in ℝn: polytope volume can be estimated in time widetildeO(mnc/varepsilon2) where c<3.7 depends on the current matrix multiplication exponent and improves on the previous best bound.