The Subspace Flatness Conjecture and Faster Integer Programming
This resolves a key conjecture in optimization theory, enabling faster algorithms for integer programming problems, though it is an incremental advance building on prior work.
The paper tackles the Subspace Flatness Conjecture in integer programming, proving that the covering radius bound is O(log^3(2n)) times the volume-based lower bound, which leads to a randomized algorithm with (log(2n))^{O(n)} time complexity and improves the flatness constant to O(n log^2(2n)).
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ász proved that $μ(Î,K) \leq n \cdot μ_{KL}(Î,K)$ and the Subspace Flatness Conjecture by Dadush (2012) claims a $O(\log(2n))$ factor suffices, which would match the lower bound from the work of Kannan and Lovász. We settle this conjecture up to a constant in the exponent by proving that $μ(Î,K) \leq O(\log^{3}(2n)) \cdot μ_{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(2n))^{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 \log^{2}(2n))$, improving on the previous bound of $O(n^{4/3} \log^{O(1)} (2n))$.