The Subspace Flatness Conjecture and Faster Integer ProgrammingOberseminar Discrete Optimization

by Thomas Rothvoß (University of Washington)

Monday May 12, 2025, 6:15 PM → 7:15 PM Europe/Berlin

Arithmeum, Lennéstr., 2 - Seminarraum (Arithmeum / Research Institute for Discrete Mathematics)

In a seminal paper, Kannan and Lovász (1988) considered a quantity μKL(Λ, K) which denotes the best volume-based lower bound on the covering radius μ(Λ, K) of a convex body K with respect to a lattice Λ. Kannan and Lov´asz proved that μ(Λ, K) ≤ n · μKL(Λ, K) and the Subspace Flatness Conjecture by Dadush (2012) claims a O(log n) factor suffices, which would match the lower bound from the work of Kannan and Lov´asz. We settle this conjecture up to a constant in the exponent by proving that μ(Λ, K) ≤ O(log3(n)) · μKL(Λ, K). Our proof is based on the Reverse Minkowski Theorem due to Regev and Stephens-Davidowitz (2017). Following the work of Dadush (2012, 2019), we obtain a (log n)O(n)-time randomized algorithm to solve integer programs in n variables.
Another implication of our main result is a near-optimal flatness constant of O(n log3(n)).

This is joint work with Victor Reis.