The Subspace Flatness Conjecture and Faster Integer Programming
Victor Reis, Thomas Rothvoss
Abstract
In a seminal paper, Kannan and Lovász (1988) considered a quantity which denotes the best volume-based lower bound on the covering radius of a convex body K with respect to a lattice . Kannan and Lovász proved that and the Subspace Flatness Conjecture by Dadush (2012) claims a 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 . Our proof is based on the Reverse Minkowski Theorem due to Regev and Stephens-Davidowitz (2017). Following the work of Dadush , we obtain a -time randomized algorithm to solve integer programs in n variables. Another implication of our main result is a near-optimal flatness constant of .
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
9 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Integer programs with nearly totally unimodular matrices: the cographic case cites Parameterized algorithms for block-structured integer programs with large entries
- A parameterized linear formulation of the integer hull cites Parameterized algorithms for block-structured integer programs with large entries
- A parameterized linear formulation of the integer hull cites Integer programs with nearly totally unimodular matrices: the cographic case
Cited by top-tier papers9
- Parameterized algorithms for block-structured integer programs with large entriesJana Cslovjecsek, Martin Koutecký, Alexandra Lassota, Michal Pilipczuk et al.SODA 2024 · 7 citations
- Integer programs with nearly totally unimodular matrices: the cographic caseManuel Aprile, Samuel Fiorini, Gwenaël Joret, Stefan Kober et al.SODA 2025 · 3 citations
- Dense Subgraph Discovery Meets Strong Triadic ClosureChamalee Wickrama Arachchi, Iiro Kumpulainen, Nikolaj TattiKDD 2024 · 2 citations
- From Your Block to Our Block: How to Find Shared Structure Between Stochastic Block Models over Multiple GraphsIiro Kumpulainen, Sebastian Dalleiger, Jilles Vreeken, Nikolaj TattiAAAI 2025 · 1 citation
- A parameterized linear formulation of the integer hullFriedrich Eisenbrand, Thomas RothvossSODA 2026 · 1 citation
Related papers
- Reducing isotropy and volume to KLS: an o*(n3ψ2) volume algorithmHe Jia, Aditi Laddha, Yin Tat Lee, Santosh S. VempalaSTOC 2021 · 12 citations
- A 2n/2-Time Algorithm for -SVP and -Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVPDivesh Aggarwal, Zeyong Li, Noah Stephens-DavidowitzEUROCRYPT 2021 · 9 citations
- Forall-exist statements in pseudopolynomial timeEleonore Bach, Friedrich Eisenbrand, Thomas Rothvoss, Robert WeismantelSODA 2025 · 1 citation
- Minimizing Convex Functions with Integral MinimizersHaotian JiangSODA 2021 · 14 citations
- An Improved Bound for the Beck-Fiala ConjectureNikhil Bansal, Haotian JiangFOCS 2025 · 2 citations
