Department of Computer Science

Lattices, Convexity and AlgorithmsCSCIGA 3033013 
Spring 2013 
Lectures 
Tuesday 57pm. CIWW 312. 
Office Hours 
Monday 45pm. 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 Latticebased Cryptography (and a PowerPoint presentation) 
Date  Class Topic 
January 29  Introduction, Lattices and their Bases, GramSchmidt 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 