The Subspace Flatness Conjecture and Faster Integer Programming

arXiv2303.14605MaRDI QIDQ6430861

Author name not available (Why is that?)

Publication date: 25 March 2023

Abstract: In a seminal paper, Kannan and Lov'asz (1988) considered a quantity $m{u}_{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 Lov'asz proved that $mu(Lambda,K)leqncdotm{u}_{KL}(Lambda,K)$ and the Subspace Flatness Conjecture by Dadush (2012) claims a $O(logn)$ 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 $mu(Lambda,K)leqO(lo{g}^3(n))cdotm{u}_{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 $(logn{)}^{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(nlo{g}^4(n))$.

This page was built for publication: The Subspace Flatness Conjecture and Faster Integer Programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6430861)