Journal of the ACM · 23 Apr 2026
Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms
He Jiah-index 0, Aditi Laddha, Yin Tat Lee, Santosh Vempalah-index 4
Citations by database
Each database indexes a different set of journals, preprints and books, so they are shown side by side rather than blended.
- OpenAlex28
- OpenCitations0
- Crossref0
Citations per year
The current year is still counting.
- 2026 so far0
Abstract
We show that the volume of a convex body in \(\mathbb {R}^{n}\) specified in the general membership oracle model can be computed to within relative error \(\varepsilon \gt 0\) using \(\widetilde{O}(n^{3.5}\psi ^{2} + n^3/\varepsilon ^{2})\) oracle queries, where \(\psi\) is the KLS constant. With the current bound of \(\psi =\widetilde{O}(1)\) , this gives an \(\widetilde{O}(n^{3.5} + n^3/\varepsilon ^{2})\) algorithm, improving on the Lovász-Vempala \(\widetilde{O}(n^{4}/\varepsilon ^{2})\) algorithm from 2003. The main new ingredient is an \(\widetilde{O}(n^{3}\psi ^{2})\) algorithm for isotropic transformation of a well-rounded convex body; we apply this iteratively to isotropize a general convex body. Following this, we can apply the \(\widetilde{O}(n^{3}/\varepsilon ^{2})\) 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 \(\mathbb {R}^{n}\) : polytope volume can be estimated in time \(\widetilde{O}(mn^{c+0.5}+mn^{c}/\varepsilon ^{2})\) where c < 3.2 depends on the current matrix multiplication exponent and also improves on the previous best bound.
What the data shows
- OpenAlex counts 28 citations, the most of the databases. The others count 0.
- Santosh Vempala has the highest h-index among the authors (4).
Graph
This paper in the middle, its authors and their most-cited papers below, the papers it cites to the left and the papers citing it to the right. The timeline lays every paper out by year.
Select a node for its details. Drag to pan, scroll to zoom, drag a node to move it.
Start with
Cited by 0 papers
Who cites this paper, from open citation data, with Crossref's record of each; the 100 newest when there are more.
References (20)
What it cites, from open citation data, with Crossref's record of each.