## Class Materials

#### Lectures

- 09/06/2017:
**Intro, Tug of War sketch**
(scribe)
- 09/11/2017:
**Tug of War ++, CountSketch** (scribe)
- 09/13/2017:
**CountSketch, Chernoff bounds, $\ell_0$ sampling** (scribe)
- 09/18/2017:
**Dynamic
graphs in streaming** (scribe)
- 09/20/2017:
**Measure concentration** (Ilya's notes, scribe)
- Jiri Matousek, “Lectures on Discrete Geometry”, Chapter 14
- Keith Ball, “An Elementary Introduction to Modern Convex Geometry”, Lecture 1 and Lecture 7 (link)

- 09/25/2017:
**Dimension reduction, fast dimension reduction** (Ilya's notes, scribe)
- dimension reduction: Lectures 7,8,9 from here
- proof of JL:
see Piotr
Indyk's notes
- Tail bounds for Chi-squared: see here, Lemma 1
- Bernstein's inequality: see here, Equation (2.20)

- 09/27/2017:
**Fast dimension reduction, randomized numerical linear algebra** (Ilya's notes, scribe)
- A lecture on oblivious subspace embeddings from a class of Ankur Moitra
- David Woodruff, “Sketching as a Tool for Numerical Linear Algebra”, see here

- 10/02/2017:
**Randomized numerical linear algebra, nearest neighbor search** (Ilya's notes, scribe)
- SETH-hardness of the exact NNS can be found here
- For a general reduction from “near
*est*” to “near” (and for a great survey of the state of affairs with high-dimensional NNS as of 2012), see here

- 10/04/2017:
**Nearest neighbor search, locality-sensitive hashing** (Ilya's notes, scribe)
- 10/09/2017:
**Locality-sensitive hashing** (Ilya's notes, scribe)
- 10/11/2017:
**SDP algorithms: Max-Cut problem** (scribe)
- 10/16/2017:
**SDP algorithms: graph coloring** (scribe)
- 10/18/2017:
**Spectral graph algorithms: linear algebra** (scribe)
- 10/23/2017:
**Spectral graph algorithms: spectrum of
adjacency matrix** (scribe)
- 10/25/2017:
**Spectral graph algorithms: Cheeger
inequality** (scribe)
- 10/29/2017:
**Spectral graph algorithms (multi-way cuts). Sparsest cut** (scribe)
- 11/1/2017:
**Sparsest cut, metric embeddings** (scribe)
- 11/8/2017:
**Metric embeddings, Bourgain's theorem** (scribe)
- 11/13/2017:
**Padded decompositions, multicut** (scribe)
- 11/15/2017:
**Hierarchical decompositions, distance oracles** (scribe)
- 11/20/2017:
**Distance oracles: Thorup-Zwick** (scribe)
- 11/27/2017:
**Discrepancy, “Six Standard Deviations Suffice”** (scribe)
- 11/29/2017:
**Discrepancy: constructive** (scribe)
- 12/4/2017:
**Recap** (scribe)