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