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

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.