# The Subspace Flatness Conjecture and Faster Integer Programming

arXiv: https://arxiv.org/abs/2303.14605 · HTML: https://mlsanity.com/paper/2303.14605/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Mar 2023.

## Built on by (most cited first, 1 of 1)

- [Correlated Mutations for Integer Programming](https://mlsanity.com/paper/2506.22526/) (2025)

## Abstract (arXiv)

In a seminal paper, Kannan and Lov'asz (1988) considered a quantity μKL(Lambda,K) which denotes the best volume-based lower bound on the covering radius μ(Lambda,K) of a convex body K with respect to a lattice Lambda. Kannan and Lov'asz proved that μ(Lambda,K) ≤ n · μKL(Lambda,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'asz. We settle this conjecture up to a constant in the exponent by proving that μ(Lambda,K) ≤ O(log3(2n)) · μKL (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(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 log2(2n)), improving on the previous bound of O(n4/3 logO(1) (2n)).