Algorithmic Geometry of Numbers

Feb-May 2010

Schedule

• Lecture 1: Introduction and basic definitions from Geometry of Numbers, Minkowski's convex body theorem, first and second inequality; and an application of these to a theorem in number theory.
• Lecture 2: Planar Lattice Reduction (Gauss's algorithm) and its weakening; Eisenbrand's algorithm for obtaining shortest vector using extended Euclidean algorithm..
• Lecture 3: Reductions in higher dimensions: LLL reduced basis, definition and properties.
• Lecture 4: A variant of the LLL algorithm.
• Lecture 5: Kannan's algorithm for shortest vector problem (SVP).
• Lecture 6: Sieving algorithms for SVP.
• Lecture 7: The Closest Vector Problem and its relation to SVP.
• Lecture 8: Exact (Kannan's) and approximate algorithms (Babai's) for CVP.
• Lecture 9&10: Deterministic single exponential time algorithm for CVP by Micciancio and Voulgaris.
• Lecture 11: Dual Lattices, and basic transference theorems.
• Lecture 12: Some Fourier Analysis, and GapCVP(\sqrt{n}) in co-NP

Sources

• Kannan's notes on Algorithmic Geometry of Numbers.
• Oded Regev's lecture notes on Lattices in Computer Science.
• F. Eisenbrand's survey: Integer Programming and Algorithmic Geometry of Numbers.
• Carl Ludwig Siegel's Lectures on the Geometry of Numbers.
• Chapters 8 & 9 of C. Yap's Fundamental Problems in Algorithmic Algebra.
• The LLL Algorithm Survey and Applications.