Reducing Isotropy and Volume to KLS: An O(n^3ψ^2) Volume Algorithm
share
We show that the the volume of a convex body in ℝ^n in the general membership oracle model can be computed with O(n^3ψ^2/ε^2) oracle queries, where ψ is the KLS constant (O suppresses polylogarithmic terms. O^*suppresses dependence on error parameters as well as polylogarithmic terms.). With the current bound of ψ≲ n^1/4, this gives an O(n^3.5/ε^2) algorithm, the first general improvement on the Lovász-Vempala O(n^4/ε^2) algorithm from 2003. The main new ingredient is an O(n^3ψ^2) algorithm for isotropic transformation, following which we can apply the O(n^3/ε^2) volume algorithm of Cousins and Vempala for well-rounded convex bodies. A positive resolution of the KLS conjecture would imply an O(n^3/ϵ^2) volume algorithm. 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 O(mn^c/ε^2) where c<3.7 depends on the current matrix multiplication exponent and improves on the the previous best bound.
READ FULL TEXT