Lectures and Scribes

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:

• lecture 5 from Jelani's class below.

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

• lecture 3, and lecture 5 from Jelani Nelson's class.

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:

• blog post on p-moments via Precision Sampling.
• lecture 6 from Jelani Nelson's class.
• Graph Stream Algorithms: a Survey, by Andrew McGregor.

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

• counting triangles: Graph Stream Algorithms: a Survey, by Andrew McGregor
• dynamic graphs: lecture 6 from Jelani Nelson's class.

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:

• dimension reduction: Lecture 9 from Jelani Nelson's class.
• Lecture 5 from Piotr Indyk and Ronitt Rubinfeld's class.
• proof of JL: see Piotr Indyk's writeup.

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

• Lecture 12 from Jelani Nelson's class.

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:

• LSH: see this book chapter, or wiki webpage.

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

• for data-dependent hashing, see this blog post or the full article (may be technically hard to read).

Oct 20: compressed sensing from JL

• lecture notes
• Lecture 16 from Jelani Nelson's class
• A Mathematical Introduction to Compressed Sensing by Foucart, Rahut
• RIP from JL

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

• lecture 13, and lecture 14 from Jelani Nelson's class.

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

• LSR: lecture 14 from Jelani Nelson's class.
• metric embeddings: see lecture 1 and 2 from Goemans' class at MIT.

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

• see the paper by Indyk and Thaper.

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

• lecture 7 from Paul Beame's class at UW.

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

• paper by Valiant and Valiant (see section 3).
• lecture 15 of Paul Beame's class.

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

• lecture 15 of Paul Beame's class.
• lecture 12 (notes) from the Piotr Indyk and Ronitt Rubinfeld's class.

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):

• Algorithms for Big Data (F13) , by Jelani Nelson (Harvard)
• Algorithms for Big Data, by Chandra Chekuri (UIUC)
• Sublinear Algorithms, by Piotr Indyk and Ronitt Rubinfeld (MIT)
• Sublinear and Streaming Algorithms, by Paul Beame (UW)

Surveys, expository articles:

• Data Stream Algorithms, by Amit Chakrabarti.
• Graph Stream Algorithms: a Survey, by Andrew McGregor.