[ 583D - Integer Optimization and Lattices]

Lecturer: Thomas Rothvoss

Course information

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)