| Date | Topic | Scribe notes | Additional readings/references |
|---|---|---|---|
| Jan 7 | Introduction, Morris counter, median of means |
Lecture 1 | [Morris '78] |
| Jan 10 | Distinct elements |
Lecture 2 | [Flajolet-Martin '85] |
| Jan 14 | AMS sketch for second moment, Johnson-Lindenstrauss lemma |
Lecture 3 | |
| Jan 17 | l_p norms for p < 2, pseudorandomness |
Lecture 4 | |
| Jan 24 | l_p norms for p > 2 |
Lecture 5 | |
| Jan 28 | heavy hitters |
Lecture 6 | |
| Jan 31 | CountSketch |
||
| Feb 4 | continue CountSketch, l_0 sampling |
||
| Feb 7 | start graph sketching |
||
| Feb 11 | sketching min cut, start compressive sensing |
Lecture 10 | |
| Feb 14 | compressive sensing using L_1 minimization |
Lecture 11 | |
| Feb 21 | fast algorithm for compressive sensing |
Lecture 12 | |
| Feb 25 | continue fast algorithm, start sketching for linear algebra |
Lecture 13 | |
| Feb 28 | approximate matrix product (class starts at 12:15) |
Lecture 14 | |
| Mar 11 | approximate matrix product using JL, subspace embedding |
Lecture 15 | |
| Mar 14 | regression using subspace embeddings |
Lecture 16 | |
| Mar 18 | low rank approximation using subspace embeddings |
||
| Mar 21 | continue low rank approx using embeddings, survey of sampling techniques using leverage scores |
||
| Mar 25 | Lydia's presentation |
||
| Mar 28 | presentation |
||
| Apr 1 | Akshar's presentation |
||
| Apr 4 | Xuangui's presentation |
||
| Apr 8 | Peter's presentation |
||
| Apr 11 | David's presentation |
||
| Apr 18 |