**Scribers**: please use this LaTeX template as your starting point.

- 01/22/2019:
**Intro, Morris algorithm for approx counting**(scribe in pdf and tex)- Morris: Lecture 1 from here

- 01/24/2019:
**Chernoff bound, distinct elements count**(scribe in pdf and tex)- Lecture 2 from here

- 01/29/2019:
**Impossibility results, Tug-of-War sketch for 2nd moment**(scribe in pdf and tex)- Lectures 2,3 from here

- 01/31/2019:
**Heavy hitters, CountMin, linearity**(scribe in pdf and tex)- Lectures 3,4 from here

- 02/5/2019:
**High frequency moments and precision sampling**(scribe in pdf and tex)- For the full analysis of the Fp sketch see this write-up. Section 4 presents Precision Sampling Lemma.
- Lectures 4,5 from here

- 02/7/2019:
**Dimension reduction, ell_1**(scribe in pdf and tex)- Lecture 8 from here

- 02/12/2019:
**Numerical Linear Algebra: least square regression, fast dimension reduction**(scribe in pdf and tex) - 02/14/2019:
**Numerical Linear Algebra: fast dimension reduction, ell_1 regression**(scribe in pdf and tex)- Lecture 6 from here

- 02/19/2019:
**Compressed sensing: Restricted Isometry Property**(scribe in pdf and tex)- Lecture 13 from here

- 02/21/2019:
**Compressed sensing: iterative hard thresholding**(scribe in pdf and tex)- Lectures 13, 14 from here
- In particular, for the proof of "RIP implies null-space property", see proof of Lemma 1 from this writeup (from Harvard/MIT class).

- 02/26/2019:
**Streaming for graph problems: distance, triangle count**(scribe in pdf and tex)- Lectures 5,6 from here

- 02/28/2019:
**Streaming: dynamic sampling/ell_0 sampler**(scribe in pdf and tex)- Lectures 6,7 from here

- 03/05/2019:
**Streaming for dynamic graph problems: connectivity.**(scribe in pdf and tex)- Lectures 6,7 from here

- 03/07/2019:
**Distribution testing: uniformity**(scribe in pdf and tex)- Lectures 17,18 from here

- 03/12/2019:
**Distribution testing.**(scribe in pdf and tex)- Lectures 17,18 from here

- 03/14/2019:
**Monotonicity testing. Sublinear-time graph algorithms: MST.**(scribe in pdf and tex) - 03/26/2019:
**Sublinear-time graph algorithms: MST, and Vertex Cover.**(scribe in pdf and tex) - 03/28/2019:
**Sublinear-time graph algorithms: VC. Linearity testing (BLR).**(scribe in pdf and tex) - 04/2/2019:
**Linearity testing (BLR test).**(scribe in pdf and tex)- Linearity testing: Lecture 21 from here

- 04/4/2019:
**Large-scale models: IO model, cache oblivious model.**(scribe in pdf and tex)- lectures 24, 25 from here

- 04/9/2019:
**Cache oblivious model, Parallel models.**(scribe: version 1 pdf and tex; version 2 pdf and tex) - 04/11/2019:
**MPC model: sorting.**(scribe in pdf and tex)- lecture 27 from D. Karger and A. Madry's class

- 04/16/2019:
**MPC model: graph connectivity.**(scribe in pdf and tex)- this lecture from G. Yaroslavtsev's class

- 04/18/2019:
**Learning-aware/data-dependent algorithms.**(scribe in pdf and tex)- lecture 7 from this class by P. Indyk and K. Daskalakis

- 04/23/2019:
**LSH and fruit flies.**(scribe in pdf and tex) - 04/25/2019:
**presentations. class recap.**(scribe in pdf and tex)

- Algorithmic Techniques for Massive Data, Fall'15 (previous iteration of this class)
- Sketching Algorithms for Big Data, Fall'17, Jelani Nelson (Harvard), Piotr Indyk (MIT)
- List of other similar classes