CS7880: Special Topics in Theoretical Computer Science


[Home] [Schedule]
The schedule is tentative and subjects to change (e.g. snow days)
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