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