Lune

FOCS2023Top-tier venue

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 μKL(Λ,K)\mu_{K L}(\Lambda, K) which denotes the best volume-based lower bound on the covering radius μ(Λ,K)\mu(\Lambda, K) of a convex body K with respect to a lattice Λ\Lambda. Kannan and Lovász proved that μ(Λ,K)≤n⋅μKL(Λ,K)\mu(\Lambda, K) \leq n \cdot \mu_{K L}(\Lambda, K) and the Subspace Flatness Conjecture by Dadush (2012) claims a O(log⁡(2n))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 μ(Λ,K)≤\mu(\Lambda, K) \leq O(log⁡3(2n))⋅μKL(Λ,K)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)(2012,2019), we obtain a (log⁡(2n))O(n)(\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(nlog⁡3(2n))O\left(n \log ^{3}(2 n)\right).

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

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
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers9

  1. Parameterized algorithms for block-structured integer programs with large entriesJana Cslovjecsek, Martin Koutecký, Alexandra Lassota, Michal Pilipczuk et al.SODA 2024 · 7 citations
  2. Integer programs with nearly totally unimodular matrices: the cographic caseManuel Aprile, Samuel Fiorini, Gwenaël Joret, Stefan Kober et al.SODA 2025 · 3 citations
  3. Dense Subgraph Discovery Meets Strong Triadic ClosureChamalee Wickrama Arachchi, Iiro Kumpulainen, Nikolaj TattiKDD 2024 · 2 citations
  4. 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
  5. A parameterized linear formulation of the integer hullFriedrich Eisenbrand, Thomas RothvossSODA 2026 · 1 citation

Related papers

  1. Reducing isotropy and volume to KLS: an o*(n3ψ2) volume algorithmHe Jia, Aditi Laddha, Yin Tat Lee, Santosh S. VempalaSTOC 2021 · 12 citations
  2. A 2n/2-Time Algorithm for n\sqrt{n}-SVP and n\sqrt{n}-Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVPDivesh Aggarwal, Zeyong Li, Noah Stephens-DavidowitzEUROCRYPT 2021 · 9 citations
  3. Forall-exist statements in pseudopolynomial timeEleonore Bach, Friedrich Eisenbrand, Thomas Rothvoss, Robert WeismantelSODA 2025 · 1 citation
  4. Minimizing Convex Functions with Integral MinimizersHaotian JiangSODA 2021 · 14 citations
  5. An Improved Bound for the Beck-Fiala ConjectureNikhil Bansal, Haotian JiangFOCS 2025 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines