## CSE599 - Lattices - Winter 2023

### Course information

• Class schedule: MW 10:00 - 11:20 in MLR 316
• Instructor:
Thomas Rothvoss, rothvoss@uw.edu.
Office hour: Wednesday, 12:30-1:30 in CSE 556
• TA:
• Victor Reis, voreis@cs.washington.edu. Office hour: Friday, 11AM-12PM in CSE2 153 (Gates building)
• Course description: A lattice is discrete subgroup of R^n. Lattices are fundamental objects in discrete math with
a rich set of applications to theoretical computer science, optimization and cryptography.
We will see the following in this course:
• Introduction to lattices (Minkowski's Theorems, the LLL algorithm, Knapsack cryptosystems, dual lattices, Hermite normal form, KZ-reduced basis)
• Algorithms for the Closest Vector problem (Babai's algorithm, the Voronoi cell algorithm by Micciancio and Voulgaris)
• The Transference Theorems of Banaszczyk (Fourier analysis, the discrete Gaussian, transference theorem for Euclidean norm, transference theorem for arbitrary norms)
• Khintchine's Flatness Theorem
• Lenstra's algorithm for Integer programming in fixed dimension
• Lattice problems in NP intersected coNP
• Lattice-based cryptography and Learning with Errors

• Prerequisites: This is a graduate class and a rigorous mathematical introduction to the fundamentals of lattices. A good understanding of convex geometry, probability and algorithms will be very helpful.

• Lecture notes: Lecture notes can be found here. Updates will be posted later. I would appreciate an email if you find a mistake/typo.
In case you want to read additional material, some useful sources are:
• D. Micciancio & S. Goldwasser, A Complexity of Lattice problems, Springer, 2002.
• O. Regev. Lattices in Computer Sciences. Lecture notes. 2009

• Required Work:
• Your grade will be based on homework assignments. Homeworks are due weekly on Fridays on GradeScope. I will post homework problems on this webpage. Homework due in a particular week will be posted on Friday the week before (occasionally the posted homework will contain a problem based on material covered in the upcoming Monday lecture).
• Students are expected to read the lecture notes in parallel to the lecture.
• NO EXAMS
• Collaboration policy: You may work with other students in finding solutions to homework problems, but please write up solutions on your own.
• Discussion forum: Other than in office hours, you may ask questions on course content and homework on the course discussion forum

### Covered material

1. Wednesday, Jan 4, 2023. Basics of lattices, unimodular matrices, the fundamental parallelepiped, Minkowski's First Theorem, Blichfeldt's Theorem
2. Monday, Jan 9, 2023: The shortest vector, successive minima, Dirichlet's Theorem, Minkowski's 2nd Theorem
3. Wednesday, Jan 11, 2023: The LLL-algorithm
4. Monday, Jan 16, 2023: NO CLASS (MLK day)
5. Wednesday, Jan 18, 2023: The orthogonality defect. The Knapsack crypto system
6. Monday, Jan 23, 2023. Dual lattices. HNF. Def KZ reduced basis.
7. Wednesday, Jan 25, 2023. KZ-reduced basis. Covering radius.
8. Monday, Jan 30, 2023: Covering radius and construction of lattice for which Minkowski's Thm is tight. 2^(n^2) algorithm for CVP. Baibai's algorithm.
9. Wednesday, Feb 1, 2023: The Voronoi cell algorithm
10. Monday, Feb 6, 2023: The Sieving algorithm
11. Wednesday, Feb 8, 2023: Chapter 4.1-4.3 (skipped proof of Fourier series Theorem).
12. Monday, Feb 13, 2023: Chapter 4.4 (Transference for symmetric convex bodies)
13. Wednesday, Feb 15, 2023: Chapter 4.4 and 5.1
14. Monday, Feb 20, 2023: NO CLASS (President's Day)
15. Wednesday, Feb 22, 2023: Chapter 5.2+.
16. Monday, Feb 27, 2023: Finished Chapter 5. Started with Chapter 6.
17. Wednesday, Mar 1, 2023: The shifted discrete Gaussian + approx. the function F until Chernov-Hoeffding
18. Monday, Mar 6, 2023: Finished Chapter 6. LAST DAY OF CLASS.

Last day of class will be Wednesday, Mar 8, 2022.

### Problem sets

• Homework 1, due Friday, Jan 13, 2023, 11pm on GradeScope: Please solve the problems in the linked PDF.
• Homework 2, due Friday, Jan 20, 2023, 11pm on GradeScope: Please solve the problems in the linked PDF.
• Homework 3, due Friday, Jan 27, 2023, 11pm on GradeScope: Please solve the problems in the linked PDF.
• Homework 4, due Friday, Feb 3, 2023, 11pm on GradeScope: Please solve the problems in the linked PDF.
• Homework 5, due Friday, Feb 10, 2023, 11pm on GradeScope: Please solve the problems in the linked PDF.
• Homework 6, due Friday, Feb 17, 2023, 11pm on GradeScope: Please solve the problems in the linked PDF.
• Homework 7, due Friday, Feb 24, 2023, 11pm on GradeScope: Please solve the problems in the linked PDF.
• Homework 8, due Friday, Mar 3, 2023, 11pm on GradeScope: Please solve the problems in the linked PDF.