Daniel Dadush: Integer Programming and the Kannan-Lovasz Conjecture

In this talk, I will give a (very) high-level overview of the lattice theoretic and convex geometric tools needed to solve n-variable integer programs in O(n)n time. In the process, I will introduce the Kannan-Lovasz conjecture, which posits the existence of very sparse lattice projections of lattice free convex bodies a higher dimensional strengthening of the classical atness theorem and gives a pathway to a (log n)O(n) time algorithm for IP. Time permitting, I will discuss the resolution of the KL-conjecture in the l2 setting due to Regev and Stephens-Davidowitz (STOC 2017), and the key concepts therein.