The lecture notes will be generated continuously as the course progresses.

Lecture Schedule

Lec# Date Topic Reading
1 Wednesday, 8/26/20 logistics, course topics, approximate counting (Morris Counter) vid § 2.1
2 Monday, 8/31/20 distinct elements, k-wise independence vid § 2.2.1-2.2.2
3 Wednesday, 9/2/20 geometric sampling vid § 2.2.3
Monday, 9/7/20 NO CLASS
4 Wednesday, 9/9/20 quantiles vid § 2.3
5 Monday, 9/14/20 lower bounds via compression arguments vid § 3.1
6 Wednesday, 9/16/20 lower bounds via communication complexity vid § 3.2
7 Monday, 9/21/20 linear sketching, turnstile streaming, heavy hitters vid § 4.1
8 Wednesday, 9/23/20 graph sketching vid § 4.2
9 Monday, 9/28/20 AMS sketch, Hanson-Wright inequality, Johnson-Lindenstrauss vid § 4.3.1, § 5.1
10 Wednesday, 9/30/20 decoupling, Hanson-Wright proof, ℓp norm estimation, Nisan’s PRG vid § 1, § 4.3.2-4.3.3
11 Monday, 10/5/20 Guest Lecture: Ilya Razenshteyn vid
12 Wednesday, 10/7/20 Johnson-Lindenstrauss lower bounds vid § 5.2
13 Monday, 10/12/20 JL lower bound wrap-up, Sparse Johnson-Lindenstrauss Transform vid § 5.3.1
14 Wednesday, 10/14/20 Fast Johnson-Lindenstrauss Transform, Krahmer-Ward theorem vid § 5.3.2-5.3.3
15 Monday, 10/19/20 Krahmer-Ward wrap-up, approximate matrix multiplication vid § 5.3.3-6.1.1
16 Wednesday, 10/21/20 JL moment property, subspace embeddings, sketch-and-solve vid § 6.1.2-6.3.1
17 Monday, 10/26/20 leverage score sampling, oblivious subspace embedding constructions, sketch-and-solve via AMM vid § 6.2.2-6.2.3, § 6.3.2
18 Wednesday, 10/28/20 faster iterative regression, low-rank approximation vid § 6.3.3-6.4
19 Monday, 11/2/20 projection-cost preserving sketches vid § 6.5
20 Wednesday, 11/4/20 k-means, compressed sensing, RIP, basis pursuit vid § 6.5.1-7.1.1
21 Monday, 11/9/20 iterative hard thresholding, expanders and RIP1 vid § 7.2
Wednesday, 11/11/20 NO CLASS
22 Monday, 11/16/20 suprema of gaussian processes, Dudley’s inequality, generic chaining, instance-wise bounds for random projections vid § 8.1-8.2
23 Wednesday, 11/18/20 Krahmer-Mendelson-Rauhut proof wrap-up, BPTree vid
24 Monday, 11/23/20 RIP via sampling DFT, Sparse Fourier Transform vid
Wednesday, 11/25/20 NO CLASS
25 Monday, 11/30/20
Wednesday, 12/2/20 Project presentations
Wednesday, 12/7/20 Project presentations
Wednesday, 12/9/20 Project presentations