We show that the volume of a convex body in \ (R^n \) specified in the general membership oracle model can be computed to within relative error ε > 0 using \ (O (n^3. 5 ^2 + n³/ ^2) \) oracle queries, where ψ is the KLS constant. With the current bound of \ (=O (1) \), this gives an \ (O (n^3. 5 + n³/ ^2) \) algorithm, improving 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 of a well-rounded convex body; we apply this iteratively to isotropize a general convex body. Following this, we can apply the \ (O (n^3/ ^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 \ (R^n \): polytope volume can be estimated in time \ (O (mn^c+0. 5+mn^c/ ^2) \) where c < 3. 2 depends on the current matrix multiplication exponent and also improves on the previous best bound.
Jia et al. (Sat,) studied this question.