## [ 583D - Integer Optimization and Lattices]

### Lecturer: Thomas Rothvoss

- Office: Padelford C-440

- 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**:

**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

**Homework I, due Friday, April 8, in class.**Note that 1.3 is a very hard one with extra points and I don't have a proof right now.

Solve Ex 1.1, 1.2, 1.3, 1.4 in the lecture notes.

**Homework II, due Monday, April 18, in class.**

**Solve Ex 1.5, 1.6, 1.8 in the lecture notes.****Homework III: due Friday, April 22 in class.**

Solve Ex 1.7, 1.9, 1.10 in the lecture notes.**Homework IV: due Friday, April 29 in class.**

Solve Ex 1.12, 1.13, 1.14 in the lecture notes.**Homework V: due Friday, May 6 in class**

Solve Ex 3.1, 3.2, 3.3**Homework VI: due Friday, May 13 in class**

Solve Ex 4.2, 4.3, 5.2**Homework VII: due Friday, May 20 in class**

Solve Ex 5.3, 5.5, 6.2**Homework VIII: due Friday, May 27 in class**Remark: For Ex 7.3, mu(Lambda) denotes the covering radius of lattice Lambda as defined in Chapter 7.3

Solve Ex 6.3, 7.1, 7.3

### Course calendar

- Monday, March 28: Introduction to lattices. Finished with def. of fundamental parallelepipeds
- Wednesday, March 30: Finished Sec 1.2.1, Minkowski's Theorem for general lattices
- Friday, April 1: Finished Sec 1.2, Dirichlet's Theorem
- Monday, April 4: Starting with Gram-Schmidt orthogonalization. Finished with def of coefficient-reduced
- Wednesday, April 6: Coefficient-reduction, LLL-algorithm

- Friday, April 8: Analysis of LLL-algorithm
- Monday, April 11: Orthogonality defect. Started with
Knapsack Crypto systems

- Wednesday, April 13: Finished sparse Knapsack and started
with dual lattices

- Friday, April 15: Lenstra-Schnorr Theorem and Hermite Normal Form
- Monday, April 18: Finishing Hermite Normal Form and Minkowski's 2nd Theorem
- Wedensday, April 20: Started chapter on integer programmig
in fixed dimension until proof of John's Theorem

- Friday, April 22: Finished proof of John's theorem and proof of Theorem 2.5
- Monday, April 25: Cor 2.6, Proof of Khinchine's flatness theorem
- Wednesday, April 27: Doignon's Theorem

- Friday, April 29: Bound on number of extreme points of integer hull P_I
- Monday, May 2: Start of AKS sieving algorithm for shortest vector
- Wedensday, May 4: Cont. of AKS Sieve algorithm

- Friday, May 6: CVP algorithm

- Monday: Mail part of CVP algorithm

- Wednesday, May 11: Finishing CVP algorithm. Started with
integer conic combinations.

- Friday, May 13: Eisenbrand-Shmonin Theorem on support of integer conic combinations
- Monday, May 16: Integer conic combinations from
parallelepipeds

- Wednesday, May 18: Finished Integer Conic Combinations

- Friday, May 20: Start with chapter on Banaszczyk's Transference Theorem (stopped in middle of proof of Poisson Formula)
- Monday, May 22: Continuing with Poisson Formula, discrete Gaussian.
- Wednesday, May 24: Finished Banaszczyk's Theorem.
Beginning of Discrepancy theory

- Friday, May 26: Continuation of discrepancy theory.

- Wednesday, June 1: Finished with the proof that a set system has a partial coloring of discrepancy O(sqrt{n * log(2m/n)}).
- Friday, June 3: Finished Spencer's Theorem. Constructive
coloring algorithm.

### Corrected typos in lecture notes

- Page 18: Several appearances of b_k and b_k^* were switched
- 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
- Page 38, Cor 2.6: I made the proof more formal.

- Page 39, in Lenstra's algorithm it should be ||b_i||_E instead of ||b_i||_2
- Page 44: Twice it should be a_i instead z_i
- First page of Chapter 6: Vector s has dimension d and not n.
- Page 69: For the ratio between alpha_j and alpja_j+1 it is enough to have a ratio of 1+1/d
- Page 68, Lemma 6.5: The number of columns of A is d and not n.
- Page 88: In condition (B) it should be |I| <= epsilon*n
(the n was missing)