Site menu:

Lecture notes

Notes will usually be posted before lecture.

All notes typeset in one file by Felix Zhou (2020)! [pdf]
Some notes for linear algebra background (read Section 2.1) [pdf]
Lecture 1 (May 11): Introduction [pdf]
  • course introduction
  • minimum cuts
Lecture 2 (May 13): Isolating cuts [pdf]
  • minimum Steiner cuts
Lecture 3 (May 20): Concentration inequalities [pdf]
  • Markov, Chebyshev, Chernoff
Lecture 4 (May 25): Applications of concentration inequalities [pdf]
  • graph sparsification, dimension reduction
Lecture 5 (May 27): Hashing [pdf]
  • k-wise independence, universal hash functions
Lecture 6 (June 1): Data streaming [pdf]
  • heavy hitters, distinct elements, frequency moments
Lecture 7 (June 3): Graph sketching [pdf]
  • 1-sparse recovery, l0-sampling, graph streaming
Lecture 8 (June 8): Polynomial identity testing [pdf]
  • string equality, Schwartz-Zippel lemma, parallel matching
Lecture 9 (June 10): Network coding [pdf]
  • max-info-flow-min-cut theorem, distributed algorithm
Lecture 10 (June 15): Local lemma [pdf]
  • k-SAT, palatte sparsification, algorithmic proof
Lecture 11 (June 17): Random walks [pdf]
  • fundamental theorem, Pagerank, perfect matchings in regular bipartite graphs