Reducing Isotropy and Volume to KLS: An O(n3ψ2) Volume Algorithm

He Jia, Aditi Laddha, Yin Tat Lee, Santosh S. Vempala

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.

Historical progression of complexity in high-dimensional volume computation.

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:

  1. 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.
  2. 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.
  3. 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.
Iterative isotropization process using growing balls and subspace scaling.

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

BibTeX
@inproceedings{jia2021reducing,
  author = {He Jia and Aditi Laddha and Yin Tat Lee and Santosh S. Vempala},
  title = {{Reducing Isotropy and Volume to KLS: An O(n3ψ2) Volume Algorithm}},
  booktitle = {STOC},
  year = {2021},
  doi = {10.1145/3406325.3451018},
}
Figure