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

Abstract

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 $\epsilon$ using $\tilde{O}(n^{3.5}\ddot{I}{ˆ}^2+n^3/{\epsilon }^2)$ oracle queries, where $\ddot{I}ˆ$ is the KLS constant. With the current bound of $\ddot{I}ˆ=\tilde{O}(1)$, this gives an $\tilde{O}(n^{3.5}+n^3/{\epsilon }^2)$ algorithm, improving on the Lovász-Vempala $\tilde{O}(n^4/{\epsilon }^2)$ algorithm from 2003. The main new ingredient is an $\tilde{O}(n^3\ddot{I}{ˆ}^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 $\tilde{O}(n^3/{\epsilon }^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 $\tilde{O}(m{n}^c/{\epsilon }^2)$ where $c<3.7$ depends on the current matrix multiplication exponent and improves on the previous best bound.

21 pages, 1 figure; updated with corrected proofs