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

Understand

We show that the volume of a convex body in $\mathbb{R}^{n}$ in the general membership oracle model can be computed to within relative error $\varepsilon$ 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\'{a}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 isotropicize 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.