The Subspace Flatness Conjecture and Faster Integer Programming

In a seminal paper, Kannan and Lovász (1988) considered a quantity $\mu_{K L}(\Lambda, K)$ which denotes the best volume-based lower bound on the covering radius $\mu(\Lambda, K)$ of a convex body K with respect to a lattice $\Lambda$. Kannan and Lovász proved that $\mu(\Lambda, K) \leq n \cdot \mu_{K L}(\Lambda, K)$ and the Subspace Flatness Conjecture by Dadush (2012) claims a $O(\log (2 n))$ 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 $\mu(\Lambda, K) \leq$ $O\left(\log ^{3}(2 n)\right) \cdot \mu_{K L}(\Lambda, 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 (2 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\left(n \log ^{3}(2 n)\right)$.

Authors

• Victor Reis
• Thomas Rothvoss

Keywords

• Integer programming
• Computer science
• Lattices
• Conjecture
• Exponent
• Running Time
• Ellipsoid
• Set Of Equations
• Examples Of Applications
• Convex Set
• Triangle Inequality
• Classical Results
• Mean Width
• Standard Argument
• Induction Step
• Lattice Points
• Barycenter
• Solid Spheres
• Short Vector
• Stable Lattice