UWashington-PIMS Mathematics Colloquium: Thomas Rothvoss

In a seminal paper, Kannan and Lovász (1988) considered a quantity  ${\mu }_{KL}(\mathrm{\Lambda },K)$which denotes the best volume-based lower bound on the covering radius  $\mu (\mathrm{\Lambda },K)$of a convex body $K$with respect to a lattice $\mathrm{\Lambda }$. Kannan and Lovász proved that  $\mu (\mathrm{\Lambda },K)\le n\cdot {\mu }_{KL}(\mathrm{\Lambda },K)$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 $\mu (\mathrm{\Lambda },K)\le O({\log }^3(n))\cdot {\mu }_{KL}(\mathrm{\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 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(n{\log }^3(n))$.

This is joint work with Victor Reis.