[ 583D - Integer Optimization and Lattices]

Lecturer: Thomas Rothvoss

• Office hours: Monday 2:30pm-3:30pm and Wednesday 2:30pm-3:30pm
• Email: rothvoss@uw.edu

Course information

• Class schedule: MWF 1:30pm - 2:20pm in PDL C401
• Description: This is a math graduate topics course on lattices and integer optimization. A detailed syllabus can be found here.
• Prerequisites: A basic understanding in algorithms and convex geometry will be very helpful.
• Required Work:
• Your grade will be based on homework assignments. Homeworks are due weekly on Fridays in class. The problems will be posted at the latest after the Monday lecture of the week in which the homework is due.
• NO EXAMS
• Lecture notes

Homework

1. Homework I, due Friday, April 8,  in class.
Solve Ex 1.1, 1.2, 1.3, 1.4 in the lecture notes.
Note that 1.3 is a very hard one with extra points and I don't have a proof right now.
2. Homework II, due Monday, April 18, in class.
Solve Ex 1.5, 1.6, 1.8 in the lecture notes.
3. Homework III: due Friday, April 22 in class.
Solve Ex 1.7, 1.9, 1.10 in the lecture notes.
4. Homework IV: due Friday, April 29 in class.
Solve Ex 1.12, 1.13, 1.14 in the lecture notes.
5. Homework V: due Friday, May 6 in class
Solve Ex 3.1, 3.2, 3.3
6. Homework VI: due Friday, May 13 in class
Solve Ex 4.2, 4.3, 5.2
7. Homework VII: due Friday, May 20 in class
Solve Ex 5.3, 5.5, 6.2
8. Homework VIII: due Friday, May 27 in class
Solve Ex 6.3, 7.1, 7.3
Remark: For Ex 7.3, mu(Lambda) denotes the covering radius of lattice Lambda as defined in Chapter 7.3

Course calendar

1. Monday, March 28: Introduction to lattices. Finished with def. of fundamental parallelepipeds
2. Wednesday, March 30: Finished Sec 1.2.1, Minkowski's Theorem for general lattices
3. Friday, April 1: Finished Sec 1.2, Dirichlet's Theorem
4. Monday, April 4: Starting with Gram-Schmidt orthogonalization. Finished with def of coefficient-reduced
5. Wednesday, April 6: Coefficient-reduction, LLL-algorithm
6. Friday, April 8: Analysis of LLL-algorithm
7. Monday, April 11: Orthogonality defect. Started with Knapsack Crypto systems
8. Wednesday, April 13: Finished sparse Knapsack and started with dual lattices
9. Friday, April 15: Lenstra-Schnorr Theorem and Hermite Normal Form
10. Monday, April 18: Finishing Hermite Normal Form and Minkowski's 2nd Theorem
11. Wedensday, April 20: Started chapter on integer programmig in fixed dimension until proof of John's Theorem
12. Friday, April 22: Finished proof of John's theorem and proof of Theorem 2.5
13. Monday, April 25: Cor 2.6, Proof of Khinchine's flatness theorem
14. Wednesday, April 27: Doignon's Theorem
15. Friday, April 29: Bound on number of extreme points of integer hull P_I
16. Monday, May 2: Start of AKS sieving algorithm for shortest vector
17. Wedensday, May 4: Cont. of AKS Sieve algorithm
18. Friday, May 6: CVP algorithm
19. Monday: Mail part of CVP algorithm
20. Wednesday, May 11: Finishing CVP algorithm. Started with integer conic combinations.
21. Friday, May 13: Eisenbrand-Shmonin Theorem on support of integer conic combinations
22. Monday, May 16: Integer conic combinations from parallelepipeds
23. Wednesday, May 18: Finished Integer Conic Combinations
24. Friday, May 20: Start with chapter on Banaszczyk's Transference Theorem (stopped in middle of proof of Poisson Formula)
25. Monday, May 22: Continuing with Poisson Formula, discrete Gaussian.
26. Wednesday, May 24: Finished Banaszczyk's Theorem. Beginning of Discrepancy theory
27. Friday, May 26: Continuation of discrepancy theory.
28. Wednesday, June 1: Finished with the proof that a set system has a partial coloring of discrepancy O(sqrt{n * log(2m/n)}).
29. Friday, June 3: Finished Spencer's Theorem. Constructive coloring algorithm.

Corrected typos in lecture notes

1. Page 18: Several appearances of b_k and b_k^* were switched
2. Page 35, last paragraph of proof of Theorem 2.5: The distance between consecutive hyperplanes is not 1/ ||b_n^*||_2, but ||b_n^*||_2
3. Page 38, Cor 2.6: I made the proof more formal.
4. Page 39, in Lenstra's algorithm it should be ||b_i||_E instead of ||b_i||_2
5. Page 44: Twice it should be a_i instead z_i
6. First page of Chapter 6: Vector s has dimension d and not n.
7. Page 69: For the ratio between alpha_j and alpja_j+1 it is enough to have a ratio of 1+1/d
8. Page 68, Lemma 6.5: The number of columns of A is d and not n.
9. Page 88: In condition (B) it should be |I| <= epsilon*n (the n was missing)