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:
- 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
- Wednesday, Jan 4, 2023. Basics of lattices, unimodular
matrices, the fundamental parallelepiped, Minkowski's First
Theorem, Blichfeldt's Theorem
- Monday, Jan 9, 2023: The shortest vector, successive minima,
Dirichlet's Theorem, Minkowski's 2nd Theorem
- Wednesday, Jan 11, 2023: The LLL-algorithm
- Monday, Jan 16, 2023: NO CLASS (MLK day)
- Wednesday, Jan 18, 2023: The orthogonality defect. The
Knapsack crypto system
- Monday, Jan 23, 2023. Dual lattices. HNF. Def KZ reduced
basis.
- Wednesday, Jan 25, 2023. KZ-reduced basis. Covering radius.
- 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.
- Wednesday, Feb 1, 2023: The Voronoi cell algorithm
- Monday, Feb 6, 2023: The Sieving algorithm
- Wednesday, Feb 8, 2023: Chapter 4.1-4.3 (skipped proof of
Fourier series Theorem).
- Monday, Feb 13, 2023: Chapter 4.4 (Transference for symmetric
convex bodies)
- Wednesday, Feb 15, 2023: Chapter 4.4 and 5.1
- Monday, Feb 20, 2023: NO CLASS (President's Day)
- Wednesday, Feb 22, 2023: Chapter 5.2+.
- Monday, Feb 27, 2023: Finished Chapter 5. Started with Chapter
6.
- Wednesday, Mar 1, 2023: The shifted discrete Gaussian +
approx. the function F until Chernov-Hoeffding
- 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.
You can check your points on the GradeScope webpage.
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.