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.

Introduction
Outline
Problem
Progress
KannanLovasz conjecture
Feasibility
Lattices
General Norms
Ellipsoids
Shortest Vector
Closest Vector
Recent Progress
Lattice Enumeration
Covering Radius
Integer Points
Duality Relation
The Problem