Department of Computer Science
New York University

Lattices, Convexity and Algorithms

CSCI-GA 3033-013

Spring 2013


Lecture notes

Homework assignments

Some Information


Tuesday 5-7pm. CIWW 312.
Office Hours

Monday 4-5pm. CIWW 425.

Daniel Dadush, Oded Regev
Attendance, homework assignments (will require relatively lots of effort)
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