Главная
Study mode:
on
1
Introduction
2
Outline
3
Problem
4
Progress
5
KannanLovasz conjecture
6
Feasibility
7
Lattices
8
General Norms
9
Ellipsoids
10
Shortest Vector
11
Closest Vector
12
Recent Progress
13
Lattice Enumeration
14
Covering Radius
15
Integer Points
16
Duality Relation
17
The Problem
Description:
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.

Daniel Dadush- Integer Programming and the Kannan-Lovasz Conjecture

Hausdorff Center for Mathematics
Add to list
0:00 / 0:00