# Recent Progress on Integer Programming and Lattice Problems New Conjectures in the Geometry of Numbers Daniel Dadush Centrum Wiskunde & Informatica (CWI) Oded Regev New York University Talk Outline 1. A Reverse Minkowski Inequality & its conjectured Strengthening. 2. Strong Reverse Minkowski implies the Kannan & Lovsz conjecture for .

3. From Decomposing Integer Programs to the general Kannan & Lovsz conjecture. Lattices The standard integer lattice . 2 1

Lattices A lattice is for a basis . denotes the lattice generated by . Note: a lattice has many 1 equivalent bases. 1

2 2 2 Lattices A lattice is for a basis . denotes the lattice generated by .

The determinant of 1 is . 2 Lattices A lattice is for a basis . denotes the lattice generated by .

The determinant of 1 is . Equal to volume of any tiling set. 2 Lattices A lattice is for a basis .

The dual lattice is is generated by . The identity holds. Lattices A lattice is for a basis . The dual lattice is is generated by . 1

2 T T T

T T =0 =1 =2 =3 =4 Reversing Minkowskis Convex Body Theorem Minkowskis Convex Body Theorem Theorem [Minkowski]: For an -dimensional symmetric convex body and lattice , we have that

0 Minkowskis Convex Body Theorem Theorem [Minkowski]: For an -dimensional symmetric convex body and lattice , we have that Question: Is the above lower bound also

close to being an upper bound? Minkowskis Convex Body Theorem Theorem [Minkowski]: For an -dimensional symmetric convex body and lattice , we have that Clearly NO! 0

Minkowskis Convex Body Theorem Theorem [Minkowski]: For an -dimensional symmetric convex body and lattice , we have that 0

Can we strengthen the lower bound? Points all lie in a lattice subspace. Reverse Minkowski Inequality For a symmetric convex body and lattice , let

0 is a lattice subspace of if . Reverse Minkowski Inequality For a symmetric convex body and lattice , let

0 Is this bound any better? Weak Reverse Minkowski For a symmetric convex body and lattice , let Let denote the unit Euclidean ball. Theorem [D.,Regev `16]: For an -dimensional lattice

. Furthermore, for any symmetric convex body . Strong Reverse Minkowski For a symmetric convex body and lattice , let Let denote the unit Euclidean ball. Conjecture [D.,Regev `16]: For an -dimensional lattice . Furthermore, for any symmetric convex body

. Tight example: and . Successive Minima Symmetric convex body and lattice in . 2 1 2 0 1 -

Minkowskis Second Theorem Symmetric convex body and lattice in . 2 1 2 0 1 - Lattice points bounds via Minima

Theorem [Henk `02]: 0 Proof of Weak Minkowski Must show If , then is lower dimensional and we can induct. If , then we have that

(by Henk) (by Minkowski) The Kannan & Lovsz conjecture for covering radius Let , i.e. the farthest distance from the lattice.

Main question: How to get good lower bounds on the covering Lower bounds for covering radius Lemma: 1

2 T T T =1 T =2 =3 =4 Lower bounds for covering

radius Lemma: Since , Lower bounds for covering radius Lemma: Let denote the orthogonal

projection onto a -dimensional subspace (*). Then . Pf: For the first inequality, since orthogonal projections shrink distances we get The second equality follows from the identity . Kannan & Lovsz for Theorem [Kannan-Lovasz `88]:

Kannan & Lovsz for Conjecture [Kannan-Lovsz `88]: Remark: implies that there are very good NPcertificates for showing that the covering radius is large. Reverse Minkowski vs Kannan & Lovsz vo l ( ) MB ( 2 , ) =max max 2

0 . . dim ( ) = d 2 det ( ) Theorem [D. Regev `16]:

If for any -dimensional lattice for a non-decreasing function , then the Kannan & Lovsz conjecture for holds with bound . Main Approach 1. Use convex programming relaxation for s.t. 2. Use Reverse Minkowski to formulate an approximate dual to the above program.

3. Round / massage optimal dual solution to get the subspace . A Sufficient Conjecture s.t. To formulate the required dual for the above program, we can rely on the following weaker conjecture: Conjecture [D. Regev `16]:

The Relaxed Program s.t. We relax the above using the following weaker constraints where , where is any orthonormal basis of . This relaxation makes the value of the program drop by at most an factor (the Reverse Minkowski bound). The Dual Program

s.t. psd. The strong dual for the above program is s.t. Here we range over all finite , where for , is a lattice subspace of , and is a PSD matrix with image . The Dual Program

s.t. Theorem [D., Regev `16]: above value is at most Corresponds to setting and projection on . Main idea: disentangle the subspaces via uncrossing. The Dual Program

s.t. Theorem [D., Regev `16]: above value is at most Implies Kannan & Lovsz bound of . (note above programs approximate ) Integer Programming and the general Kannan & Lovsz conjecture Anatomy of an IP Algorithm

Problem: Find point in or decide that is integer free. Anatomy of an IP Algorithm

Problem: Find point in or decide that is integer free. Anatomy of an IP Algorithm

Main dichotomy: 1. Either contains a deep integer point: find by rounding from center of .

Anatomy of an IP Algorithm 2 = 2 subproblems 2 = 1

Main dichotomy: 1. Either contains a deep integer point: 2. find by rounding from center of . is flat: decompose feasible region into lower dimensional subproblems and recurse. IP Algorithms Time

Space Authors Lenstra 83 Kannan 87 Hildebrand Kppe 10 D. Peikert Vempala 11, D. 12

barrier: dont know how to create less than subproblems per dimension IP Algorithms Time Space Authors Lenstra 83 Kannan 87 Hildebrand Kppe

10 D. Peikert Vempala 11, D. 12 Conjecture Kannan & Lovsz `88: subproblems per dimension should be possible! General Covering Radius & Deep Points The covering radius of with respect to is

or, smallest scaling such that every shift contains an integer point. 2 General Covering Radius & Deep Points

The covering radius of with respect to is or, smallest scaling such that every shift contains an integer point. 2 ( , ) >1 +

2 General Covering Radius & Deep Points The covering radius of with respect to is ( , ) =2 2 2 2

General Covering Radius & Deep Points Integral shifts of cover , i.e. . 2 2 General Covering Radius & Deep

Points If covering radius , then any shift of contains a deep integer point. + t1

2 General Covering Radius & Deep Points If covering radius , then any shift of contains a deep integer point. + t1

2 General Covering Radius & Deep Points If covering radius , then any shift of contains a deep integer point.

+t2 2 General Covering Radius & Deep Points If covering radius , then any shift of contains a deep integer

point. +t3 2 General Covering Radius & Deep Points Thus, if finding an

integer point in is easy. 2 General Covering Radius & Deep Points

Thus, if finding an integer point in is easy. If not, we should decompose into lower dimensional pieces 2

Lower Bounds on the Covering Radius Lemma: T .8 =.9 T =.1

o cover space, must have width at least . Khinchines Flatness Theorem Theorem: For convex, either 1. covering radius , or 2. such that has width w.r.t. :

2 Khinchines Flatness Theorem Theorem: For convex, either 1. covering radius , or 2. such that has width w.r.t. :

2 Khinchines Flatness Theorem Theorem: For convex, either 1. covering radius , or 2. such that has width w.r.t. : T

=2.3 1.5 T =.8

2 Khinchines Flatness Theorem Theorem: For convex, either 1. covering radius , or 2. such that has width w.r.t. . T =3 T

=2 T =1 T =0

2 Khinchines Flatness Theorem Theorem: cover space, suffices to scale to have width omewhere between and . Khinchines Flatness Theorem Bounds improvements for general bodies:

Khinchine `48: Babai `86: Lenstra-Lagarias-Schnorr `87: Kannan-Lovasz `88: Banaszczyk et al `99: Rudelson `00: [Khinchine `48, Babai `86, Hastad `86, LenstraLagarias-Schnorr `87, Kannan-Lovasz `88, Banaszczyk `93-96, Banaszczyk-Litvak-Pajor-Szarek `99, Rudelson `00] Khinchines Flatness Theorem Best known bounds:

Ellipsoids: Centrally Symmetric: General: [Banaszczyk `93] [Banaszczyk `96] [Banaszczyk `96, Rudelson `00] Bound conjectured to be (best possible).

How can we improve decompositions? Recursion only uses integrality of one variable at a time. Why? T =3

2.3 T =2 T =1 T =0

2 .8 Reason: Its very efficient to enumerate integer points in an interval.

How can we improve decompositions? When else is it efficient to enumerate integer points? Theorem [D. Peikert Vempala `11, D. `12]: For convex, can enumerate in time . How can we improve

decompositions? When else is it efficient to enumerate integer points? Theorem [D. Peikert Vempala `11, D. `12]: For convex, can enumerate in time . + How can we improve decompositions? Generalized Decomposition Strategy for :

Choose rank such that is small ( ) How can we improve decompositions? Generalized Decomposition Strategy for : Choose rank such that is small Enumerate and recurse on subproblems.

( ) subproblems How can we improve decompositions? How should we choose Hardest bodies to decompose satisfy , i.e. as fat as possible without containing deep points.

How can we improve decompositions? How should we choose If then also , so integer projections of are only fatter. ( ) How can we improve decompositions? How should we choose

If , then . Good choice of should approximately minimize . Volumetric bounds on the Covering Radius Lemma: If , then .

2 Volumetric bounds on the Covering Radius Lemma: If , then . Pf: Let be the cube. .

2 Volumetric bounds on the Covering Radius Lemma: If , then . Lemma: Let have rank . If , then . Pf: .

Volumetric bounds on the Covering Radius Lemma: Let have rank . If , then . Lemma: For a convex body Pf: Must scale to have volume at least in each integer projection. Kannan Lovsz Conjecture

Theorem [Kannan-Lovsz `88]: For convex, either 1. Covering radius , or 2. rank such that . In particular, Proof is constructive. Enables a time IP algorithm [D. `12]. Kannan Lovsz Conjecture Theorem [Kannan-Lovsz `88]: For convex, either 1. Covering radius , or 2. rank such that .

: 2 Kannan Lovsz Conjecture Theorem [Kannan-Lovsz `88]: For convex, either 1. Covering radius , or 2. rank such that .

: subproblems 2 Kannan Lovsz Conjecture Theorem [Kannan-Lovsz `88]: For convex, either 1. Covering radius , or 2. rank such that .

: subproblems Same as standard flatness. 2 Kannan Lovsz Conjecture

Conjecture [Kannan-Lovsz `88]: For convex, either 1. Covering radius , or 2. rank such that . In particular, An efficient enough construction would imply a time IP algorithm! Conclusions 1. New natural conjectured converse for Minkowskis convex body theorem.

2. Showed that it implies an important special case of a conjecture of Kannan & Lovsz. Open Problems 1. Prove or disprove any of the conjectures! 2. Find new applications. THANK YOU!