Class Materials


  1. 09/06/2017: Intro, Tug of War sketch (scribe)
  2. 09/11/2017: Tug of War ++, CountSketch (scribe)
  3. 09/13/2017: CountSketch, Chernoff bounds, $\ell_0$ sampling (scribe)
  4. 09/18/2017: Dynamic graphs in streaming (scribe)
  5. 09/20/2017: Measure concentration (Ilya's notes, scribe)
  6. 09/25/2017: Dimension reduction, fast dimension reduction (Ilya's notes, scribe)
  7. 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
  8. 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 “nearest” to “near” (and for a great survey of the state of affairs with high-dimensional NNS as of 2012), see here
  9. 10/04/2017: Nearest neighbor search, locality-sensitive hashing (Ilya's notes, scribe)
  10. 10/09/2017: Locality-sensitive hashing (Ilya's notes, scribe)
  11. 10/11/2017: SDP algorithms: Max-Cut problem (scribe)
  12. 10/16/2017: SDP algorithms: graph coloring (scribe)
  13. 10/18/2017: Spectral graph algorithms: linear algebra (scribe)
  14. 10/23/2017: Spectral graph algorithms: spectrum of adjacency matrix (scribe)
  15. 10/25/2017: Spectral graph algorithms: Cheeger inequality (scribe)
  16. 10/29/2017: Spectral graph algorithms (multi-way cuts). Sparsest cut (scribe)
  17. 11/1/2017: Sparsest cut, metric embeddings (scribe)
  18. 11/8/2017: Metric embeddings (scribe)