Polytope Sampling at the Speed of Isoperimetry
We give faster algorithms for sampling from the uniform distribution over a polytope. Our main result is an algorithm that, when applied to a polytope with $m$ constraints in $n$ dimensions, uses $m \cdot \mathrm{poly}\log(\frac m \delta)$ iterations, each running in time $O(mn^{\omega - 1})$, to return a sample within...