Random walks and an O∗(n5) volume algorithm for convex bodies. Random Structures and Algorithms

Given a high dimensional convex body K ⊆ IRn by a separation oracle, we can approx-imate its volume with relative error ε, using O∗(n5) oracle calls. Our algorithm also brings the body into isotropic position. As all previous randomized volume algorithms, we use “rounding ” followed by a multi-phase Monte-Carlo (product estimator) technique. Both parts rely on sampling (generating random points in K), which is done by random walk. Our algorithm introduces three new ideas: • the use of the isotropic position (or at least an approximation of it) for rounding, • the separation of global obstructions (diameter) and local obstructions (boundary problems) for fast mixing, and • a stepwise interlacing of rounding and sampling.