Department of Computer Science
|
Lattices, Convexity and AlgorithmsCSCI-GA 3033-013 |
Spring 2013 |
| Lectures |
Tuesday 5-7pm. CIWW 312. |
| Office Hours |
Monday 4-5pm. CIWW 425. |
| Instructors |
Daniel Dadush, Oded Regev |
| Requirements |
Attendance, homework assignments (will require relatively lots of effort) |
| Prerequisites |
Mathematical maturity is a must for this class. |
| Useful links |
On the Complexity of Lattice Problems with Polynomial Approximation Factors Lattice-based Cryptography (and a PowerPoint presentation) |
| Date | Class Topic |
| January 29 | Introduction, Lattices and their Bases, Gram-Schmidt orthogonalization |
| February 5 | Dual Lattices, Integer Linear Systems of Equations, Hermite Normal Form |
| February 12 | Fundamental Parallelepipeds, Determinants, Fundamental Domains, Minkowski Theorems |
| February 19 | LLL Algorithm |
| February 26 | Basic Convexity: Norms, Polarity and the Separation Theorem |
| March 5 | Ellipsoidal Approximation, The Volume Product, and the Flatness Theorem |
| March 12 | MV Algorithm for l_2 CVP |
| March 26 | The Flatness Theorem and Integer Programming |