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.

Updates to the lecture notes

• Jan 2, 2023. Chapter 1: Added a quantitative generalization of Minkowski's Theorem. Chapter 4: Subdivided lemma 4.23 in two lemmas (for easier later reference).
• Jan 11, 2023. Chapter 1. Cleaned up the coefficient reduction in the LLL-algorithm.
• Jan 20, 2023. Chapter 1. Added exercise 1.12.
• Jan 23, 2023. Chapter 1. Fixed a few things in HNF and KZ-reduction.
• Jan 30, 2023. Chapter 2. Some streamlining in Babai's algorithm and in the Voronoi-cell algorithm.
• Feb 3, 2023. Chapter 2. Fixed a coefficient in Ex 2.1.
• Feb 14, 2023. Chapter 2: changed the presentation from the OPEN Voronoi cell to the CLOSED cell. Chapter 4.4: streamlined the presentation and grouped 3 lemmas with identical assumptions together. Lower bound in Thm 4.1. needs to be 1/2 and not 1.
• Feb 21, 2023. Added Chapter 6.
• Mar 1, 2023. Fixed an inequality in proof of Lemma 6.6
• Mar 6, 2023. Added Chapters 7+8.