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

We show that the volume of a convex body in \(Rⁿ \) specified in the general membership oracle model can be computed to within relative error ε > 0 using \({O}(n3.5ψ ² + n^3/ε ²) \) oracle queries, where ψ is the KLS constant. With the current bound of \(ψ ={O}(1) \) , this gives an \({O}(n3.5 + n^3/ε ²) \) algorithm, improving on the Lovász-Vempala \({O}(n⁴/ε ²) \) algorithm from 2003. The main new ingredient is an \({O}(n³ψ ²) \) 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 \({O}(n³/ε ²) \) 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 \(Rⁿ \) : polytope volume can be estimated in time \({O}(mnc+0.5+mnᶜ/ε ²) \) where c < 3.2 depends on the current matrix multiplication exponent and also improves on the previous best bound.