Recent Progress on Integer Programming and Lattice Problems

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!

Recently Viewed Presentations

  • Finance Presentation Aidan OByrne OBK Accountants/ The Food

    Finance Presentation Aidan OByrne OBK Accountants/ The Food

    Direct Costs - Fixed/Quasi Fixed. Plant Insurance. Supervisory Labour. Factory Consumables. Promotional Costs. Reduced Margin. Racks/Ends Fees. Multibuy Accruals/Costs. Logistics. Case cost of Warehousing. Case cost of Transport/Distribution to Retailer. Fixed Overheads.
  • The Implementation of Artificial Intelligence and Temporal ...

    The Implementation of Artificial Intelligence and Temporal ...

    The Implementation of Artificial Intelligence and Temporal Difference Learning Algorithms in a Computerized Chess Program By James Mannion Computer Systems Lab 08-09 Period 3 Abstract Searching through large sets of data Complex, vast domains Heuristic searches Chess Evaluation Function Machine...
  • East Asia - shpaportal.org

    East Asia - shpaportal.org

    East Asia Issues. Trade and Prosperity. Open to the world since 1800s. Global economies- nations become dependent on each other for goods and services. Powerful economies. Jakota Triangle (Japan, Korea, and Taiwan) World Recession hurt the economies of East Asia....
  • Elements, Compounds, and Organic Compounds

    Elements, Compounds, and Organic Compounds

    Elements, Compounds, and Organic Compounds ... Atom An atom is the smallest unit or piece of an element that still has all the properties of that element. So…an atom of gold is the smallest amount of gold you can get....
  • Confident Data Integration and QC with FME - Safe Software

    Confident Data Integration and QC with FME - Safe Software

    Quality Control. Data is the foundation of every successful GIS. To ensure a reliable foundation for their GIS, organizations should have a well-designed quality assurance (QA) plan and quality control (QC) procedures integrated with the production and maintenance of GIS...
  • Topological Data Analysis

    Topological Data Analysis

    "Topology-Based Data Analysis Identifies a Subgroup of Breast Cancers With a Unique Mutational Profile and Excellent Survival." Proceedings of the National Academy of Sciences. Vol. 108, No. 17, 2011, p. 7265 - 7270. Topological analysis of very high-dimensional breast cancer...
  • St. George: 4-6 - UT Liberal Arts

    St. George: 4-6 - UT Liberal Arts

    Rosetti's St. George: 4-6 ... George and his white horse represent Christianity and the dragon represents Satan. Considered to share a common theme with Greek myth of Andromeda and her husband Perseus, slayer of Medusa. ... Considered to share a...
  • The Noble Gases - The World of Teaching

    The Noble Gases - The World of Teaching

    Uses for the Noble Gases Representative Elements 2 The electricity causes the gas to glow. Each noble gas produces a unique color. Helium glows yellow, neon glows red-orange, and argon produces a bluish-violet color. Uses for the Noble Gases Argon,...