The Subspace Flatness Conjecture and Faster Integer Programming

In a seminal paper, Kannan and Lovasz (1988) considered a quantity mu(KL)(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 Lovasz proved that mu(Lambda, K)=n.mu 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 Lovasz. We settle this conjecture up to a constant in the exponent by proving that mu(Lambda, K) <= O(log(3)(2n)).mu(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 log(3)(2n)).