The subspace flatness conjecture and faster integer programming

-
Victor Reis, IAS
Fine Hall 224

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