Daniel Dadush- Integer Programming and the Kannan-Lovasz Conjecture
Explore a high-level overview of lattice theoretic and convex geometric tools used to solve n-variable integer programs in O(n)n time. Delve into the Kannan-Lovasz conjecture, which proposes the existence of very sparse lattice projections of lattice-free convex bodies, offering a potential pathway to a (log n)O(n) time algorithm for Integer Programming. Examine the resolution of the KL-conjecture in the l2 setting by Regev and Stephens-Davidowitz (STOC 2017), and investigate key concepts such as feasibility, lattices, general norms, ellipsoids, shortest vector, closest vector, lattice enumeration, covering radius, integer points, and duality relation. Gain insights into recent progress in the field and understand the fundamental problem at hand in this comprehensive lecture on Integer Programming and the Kannan-Lovasz Conjecture.