Schedule:

Sep 8: Intro, approximate counting (Morris’ algorithm).
Lecture 1 slides. Scribe notes: [pdf], and [original tex].

Sep 10: Chernoff/Hoeffding bounds. Distinct elements count. Impossibility results.
Lecture 2 slides. Scribe notes (draft): [pdf], and [original tex].

Sep 15: Frequency moments (F_2 from Alon-Matias-Szegedy), heavy hitters (CountMin/CountSketch).
Lecture 3 slides: in pptx and in pdf. Scribes (draft): [pdf] and [tex].
related material:

Sep 17: CountSketch, Precision Sampling (for High frequency moments).
Lecture 4 slides and in pdf. Scribes (draft): [pdf] and [tex].
related material:

Sep 21 (Mon): [PS1 due].

Sep 22: High moments via Precision Sampling, Streaming for Graphs.
Lecture 5 slides and in pdf. Scribes (draft): [pdf] and [tex].
related material:

Sep 24: Streaming for Graphs: counting triangles, dynamic graphs.
Lecture 6 slides and in pdf. Scribes (draft): [pdf] and [tex].
related material:

Sep 29: dynamic graph algorithms, dimension reduction.
Lecture 7 slides and in pdf. Scribes (draft): [pdf] and [tex].
related material:
  • dynamic graphs: lecture 6 from Jelani Nelson's class.

Oct 1: dimension reduction, p-stable distributions.
Lecture 8 slides and in pdf. Scribes (draft): [pdf] and [tex]
related material:

Oct 6: fast dimension reduction.
Lecture 9 slides and in pdf. Scribes (draft): [pdf] and [tex].
Related material

Oct 7: [PS2 due].

Oct 8: sketching, nearest neighbor search.
Lecture 10 slides and in pdf. Scribes (draft): [pdf] and [tex].
related material:
  • for sketch on Hamming distance, see the original KOR paper (may be technically hard to read).

Oct 13: NNS: Locality Sensitive Hashing.
Lecture 11 slides and in pdf. Scribes (draft): [pdf] and [tex].
related material:

Oct 15: NNS: more LSH, data-dependent hashing.
Lecture 12 slides and in pdf. Scribes (draft): [pdf] and [tex].
related material:

Oct 20: compressed sensing from JL

Oct 22: More applications of dimension reduction: approximate matrix multiplication, least squares regression.
Scribes (draft): [pdf] and [tex].
Resources:

Oct 27: Least Squares Regression, metric embeddings.
Lecture 15 slides and in pdf.
Resources:

Oct 29: Earth-Mover Distance.
Lecture 16 slides and in pdf. Scribes (draft): [pdf] and [tex].
Related material:

Nov 6: sublinear time.
Lecture 17 slides and in pdf. Scribes (draft): [pdf] and [tex].
related material:

Nov 10: Distribution testing, monotonicity, and testing connectivity in graphs.
Lecture 18 slides and in pdf. Scribes (draft): [pdf] and [tex].
related material:

Nov 12: Sublinear algorithms in graphs.
Scribes (draft): [pdf] and [tex].
related material:

Nov 17: Sublinear Graph Approximation Algorithms (by Krzysztof Onak).
Lecture 20 slides.

Nov 19: Testing functions: linearity testing.
Lecture 21 scribes: [pdf] and [tex].
related material:
  • lecture 8 from the Piotr Indyk and Ronitt Rubinfeld's class.

Nov 24: Learning Fourier coefficients.
Lecture 22 slides and in pdf.

Nov 26: NO CLASS.

Dec 1:
MapReduce model, and algorithms for MapReduce model.
Guest lecture by Sergei Vassilvitskii.
[PS5 due].

Dec 3: MapReduce algorithms.
Lecture 24 slides and in pdf. Scribes: [pdf] and [tex].

Dec 8,10,11: project presentations. Sign-up here.


Dec 14: [projects due].

Study resources:
Lecture notes for similar classes at other universities (a selection of):
Surveys, expository articles: