Lecture notes
Notes will usually be posted the day before lecture.
Lecture 1 (Sep 14): introduction [pdf] [one]

Lecture 2 (Sep 16): graph spectrum [pdf] [one]

Lecture 3 (Sep 21): Cheeger's inequality [pdf] [one]

Lecture 4 (Sep 23): last eigenvalue [pdf] [one]

Lecture 5 (Sep 28): higherorder Cheeger's inequality [pdf] [one]

Lecture 6 (Sep 30): improved Cheeger's inequality [pdf] [one]

Lecture 7 (Oct 5): random walks [pdf] [one]

Lecture 8 (Oct 7): local graph partitioning [pdf] [one]

Lecture 9 (Oct 14): smallset expansion [pdf] [one]

Lecture 10 (Oct 19): expander graphs [pdf] [one]

Lecture 11 (Oct 21): smallset expanders [pdf] [one]

Lecture 12 (Oct 26): electrical networks [pdf] [one]

Lecture 13 (Oct 28): Laplacian solver [pdf] [one]

Lecture 14 (Nov 2): multiplicative weight update method [pdf] [one]

Lecture 15 (Nov 4): maximum flow [pdf] [one]

Lecture 16 (Nov 9): graph sparsification [pdf] [one]

Lecture 17 (Nov 11): spectral sparsification [pdf] [one]

Lecture 18 (Nov 16): linearsize spectral sparsification [pdf] [one]

Lecture 19 (Nov 18): interlacing polynomials [pdf] [one]

Lecture 20 (Nov 23): bipartite Ramanujan graphs [pdf] [one]

Lecture 21 (Nov 25): Weaver's conjecture [pdf] [one]

Lecture 22 (Nov 30): strongly Rayleigh measure [pdf] [one]

Lecture 23 (Dec 2): local lemma [pdf] [one]
