Reducing isotropy and volume to KLS: an o*(n3ψ2) volume algorithm

We show that the volume of a convex body in Rn in the general membership oracle model can be computed to within relative error ε using O(n3ψ2/ε2) oracle queries, where ψ is the KLS constant. With the current bound of ψ=O(no(1)), this gives an O(n3+o(1)/ε2) algorithm, the first improvement on the Lovász-Vempala O(n4/ε2) algorithm from 2003. The main new ingredient is an O(n3ψ2) algorithm for isotropic transformation, following which we can apply the O(n3/ε2) volume algorithm of Cousins and Vempala for well-rounded convex bodies. A positive resolution of the KLS conjecture would imply an O(n3/є2) volume algorithm. We also give an efficient implementation of the new algorithm for convex polytopes defined by m inequalities in Rn: polytope volume can be estimated in time O(mnc/ε2) where c<3.2 depends on the current matrix multiplication exponent and improves on the previous best bound.