CSE206A: Lattices Algorithms and Applications (Winter 2012)

Istructor: Daniele Micciancio

Section ID: 735465
Schedule: TuTh 12:30pm-1:50pm in SSB 106

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.)


Revised lecture notes and pointers to research papers and other reading material 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 external links section below.


Coursework for students enrolled in the course will include a number of individual homework assignments, and an optional group project to be executed in groups of 2 or 3 students. We will discuss possible projects later in the course.