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]
|
Lecture 2 (May 13): Isolating cuts [pdf]
|
Lecture 3 (May 20): Concentration inequalities [pdf]
|
Lecture 4 (May 25): Applications of concentration inequalities [pdf]
|
Lecture 5 (May 27): Hashing [pdf]
|
Lecture 6 (June 1): Data streaming [pdf]
|
Lecture 7 (June 3): Graph sketching [pdf]
|
Lecture 8 (June 8): Polynomial identity testing [pdf]
|
Lecture 9 (June 10): Network coding [pdf]
|
Lecture 10 (June 15): Local lemma [pdf]
|
Lecture 11 (June 17): Random walks [pdf]
|
Lecture 12 (June 22,24): Spectral graph theory [pdf]
|
Lecture 13 (June 24,29): Cheeger's inequalities [pdf]
|
Lecture 14 (June 29, July 6): Mixing time [pdf]
|
Lecture 15 (July 8, July 13): Electrical networks [pdf]
|
Lecture 16 (July 13,15): Linear programming [pdf]
|
Lecture 17 (July 15,20): Matching polytopes [pdf]
|
Lecture 18 (July 20,22): Spanning tree polytopes [pdf]
|
Lecture 19 (July 27): Linear programming duality [pdf]
|
Lecture 20 (July 29): Multiplicative weight update method [pdf]
|