Lattices in Computer Science (Fall 2004)

Lectures	Monday 12:00-15:00
Instructor	Oded Regev \| Schreiber 220 \| 5379 \| Office hours: Monday 15:00-16:00 or by appointment
Textbooks	Complexity of Lattice Problems, D. Micciancio and S. Goldwasser, An Algorithmic Theory of Numbers, Graphs, and Convexity, L. Lovasz
Lecture Notes	Lattices in Cryptography and Cryptanalysis, a course given by Daniele Micciancio Lattices and Their Application to Cryptography, a course given by Cynthia Dwork Algebra and Computation, a course given by Madhu Sudan.
Other Links	Complexity of SVP - A reader's digest, by R. Kumar and D. Sivakumar, nicely explains some of the topics covered in this class CaLC 2001, a conference on lattices, some papers can be found online Finding Small Solutions to Small Degree Polynomials, a paper by Coppersmith Twenty years of attacks on the RSA cryptosystem, a survey by Dan Boneh Lattice Basis Reduction and Integer Programming, by Karen Aardal, nicely explains fixed-dimension integer programming using LLL basis reduction

Date	Class Topic
Oct 18	Cancelled
Oct 25	Basic definitions, Gram-Schmidt orthogonalization, successive minima, lower bound on succ. minima, Minkowski's convex body theorem
Nov 1	Minkowski's first and second theorem, basic computational problems
Nov 8	LLL algorithm, Babai's nearest plane algorithm
Nov 15	Small solutions to small degree polynomials
Nov 17	Integer programming in constant dimension, basic reductions
Nov 22	Goldreich-Goldwasser proof of GapCVP in coAM
Nov 29	Ajtai-Kumar-Sivakumar SVP algorithm
Dec 6	Dual lattices
Dec 13	Fourier analysis
Dec 20	Cancelled
Dec 27	Transference theorems
Dec 31	Worst-case to average-case reduction
Jan 3	Worst-case to average-case reduction
Jan 10	CVP with preprocessing
Jan 17	Cancelled