Abstract
Estimating the volume of high-dimensional convex bodies is a fundamental challenge in computational geometry. This paper introduces a novel algorithmic framework that reduces the complexity of volume computation by linking it directly to the Kannan-Lovász-Simonovits (KLS) conjecture. By employing an iterative isotropization technique—"rounding" the body through a sequence of growing balls—the authors achieve a complexity of $\tilde{O}(n^{3.5}\psi^2)$, effectively breaking the two-decade-old $O(n^4)$ barrier. For well-rounded bodies, the complexity further improves to $\tilde{O}(n^3)$, approaching the theoretical "holy grail" of volume algorithms.
Introduction
Computing the volume of a convex body in $n$ dimensions is a problem where deterministic approaches are provably inefficient, requiring exponential time. Since the late 1980s, the field has relied on randomized Markov Chain Monte Carlo (MCMC) methods. These algorithms have seen a steady progression in efficiency, moving from $n^{23}$ in the first polynomial-time algorithm to the $O(n^4)$ standard established in 2003.
The efficiency of these randomized methods hinges on two primary factors: the speed of sampling random points within the body and the "roundness" of the body itself. A "skinny" or ill-conditioned shape slows down random walks, necessitating a pre-processing step known as "rounding" or isotropic transformation to make the body more ball-like.
Methodology: Iterative Isotropization
The core contribution of this work is a new framework for Iterative Isotropization. Rather than attempting to round the entire high-dimensional body in a single pass, the algorithm proceeds through a sequence of incremental steps:
- Growing Balls: The algorithm intersects the convex body with a ball of radius $t$. This radius is increased iteratively by a factor of $(1 + 1/\sqrt{n})$, gradually expanding to cover the entire body.
- Subspace Scaling: At each step, the algorithm analyzes the covariance matrix of the current intersection. It identifies "skinny" directions—eigenvectors with small eigenvalues—and scales them up. This "stretches" the body, maintaining its well-roundedness as the ball grows.
- KLS Integration: The sampling speed is tied to the KLS constant ($\psi$), a geometric parameter measuring partitionability. By exploiting recent breakthroughs that suggest $\psi$ is nearly constant, the authors provide tighter bounds on the algorithm's runtime.
Results and Complexity
The proposed algorithm demonstrates significant improvements across various classes of convex bodies:
- General Convex Bodies: The complexity is reduced to $\tilde{O}(n^{3.5}\psi^2)$. With current KLS bounds ($\psi \approx 1$), this effectively yields an $\tilde{O}(n^{3.5})$ algorithm.
- Well-Rounded Bodies: For bodies that are already somewhat isotropic, the complexity drops to $\tilde{O}(n^3)$.
- Polytopes: For polytopes defined by $m$ linear inequalities, the authors utilize fast matrix multiplication to achieve a runtime of $O(mn^{3.7}/\epsilon^2)$, a notable improvement over previous $O(mn^{4.5})$ bounds.
Conclusion
By decoupling the rounding process from the final volume estimation and leveraging the KLS conjecture, this work sets a new benchmark for high-dimensional geometry. The authors' iterative approach not only breaks the $O(n^4)$ barrier but also provides a clear path toward a cubic $O(n^3)$ algorithm, contingent on further refinements of the KLS constant and the ability to increase the radius more aggressively in each step.
Summary updated