CSE206A: Lattices Algorithms and Applications (Winter 2010)

Istructor: Daniele Micciancio

Section ID: 672185
Schedule: TuTh 2:00pm-3:20pm in CENTER 201

Course description

Point lattices are powerful mathematical objects that have been used to efficiently solve many important problems in computer science, most notably in the areas of cryptography and combinatorial optimization. This course gives a general introduction to the theory of point lattices, their algorithms, and a selection of applications of lattices to both cryptography and other areas of computer science, mathematics, and communication theory. Beside covering the best currently known algorithms to solve the most important lattice problems (both in their exact and approximate versions), we will touch several related areas:

Prerequisites: The main prerequisites for the course are knowledge of basic math (e.g., linear algebra, finite fields, modular arithmetic, probability, some calculus, etc.) and introductory level algorithms and complexity theory (analysis of algorithms, polynomial time solvability, NP-hardness, etc.) In particular, no prior knowledge of cryptography, advanced complexity theory, Fourier analysis, or algebraic number theory is assumed. (Though in this course you will learn a little bit of all of this.)

Lecture Notes

I am planning to cover a different selection of application from previous versions of this course. Revised lecture notes will be posted here as we cover the material in class. As a reference, see pointers to previous lecture notes and other courses in the externatl links section.


Coursework for students enrolled in the course will include 4 homework assignments, and an optional term project, and scribing one set of lecture notes if needed.

External Links


Date Class Topic
Jan 5 Basic definitions, Gram-Schmidt orthogonalization, minimum distance
Jan 7 Succesive minima, Minkowski's convex body theorem
Jan 12 Basic Algorithms: Running time of Gram-Schmidt, Hermite Normal Form, Dual lattice
Jan 14 Lattice approximation algorithms, LLL algorithm, nearest plane algorithm
Jan 19 Cancelled
Jan 21 Running time of LLL, Approximating CVP
Jan 26 Integer Programming
Jan 28 Cryptanalysis
Feb 2 Approximating SVP within subexponential factors.
Feb 4 Decoding algorithms for special lattices
Feb 9 Exact algorithms for SVP
Feb 11 Exact algorithms for CVP
Feb 16
Feb 18
Feb 23
Feb 25
Mar 2
Mar 4
Mar 9
Mar 11
Valid XHTML 1.0! Daniele Micciancio
Last Modified: April 5th, 2007