Site menu:

Lecture notes

Notes will usually be posted the day before lecture.

Lecture 1 (Sep 14): introduction [pdf] [one]
  • course information and overview
  • background in linear algebra
Lecture 2 (Sep 16): graph spectrum [pdf] [one]
  • adjacency matrix, Laplacian matrix
  • Rayleigh quotient
Lecture 3 (Sep 21): Cheeger's inequality [pdf] [one]
  • spectral partitioning algorithm
Lecture 4 (Sep 23): last eigenvalue [pdf] [one]
  • bipartiteness ratio
  • maximum cut
Lecture 5 (Sep 28): higher-order Cheeger's inequality [pdf] [one]
  • spectral embedding, k-way partitioning
Lecture 6 (Sep 30): improved Cheeger's inequality [pdf] [one]
  • higher eigenvalues
Lecture 7 (Oct 5): random walks [pdf] [one]
  • mixing time, random sampling
Lecture 8 (Oct 7): local graph partitioning [pdf] [one]
  • random walks, spectral analysis
Lecture 9 (Oct 14): small-set expansion [pdf] [one]
  • higher eigenvalues, subspace enumeration
  • unique games
Lecture 10 (Oct 19): expander graphs [pdf] [one]
  • zig-zag products
  • expander mixing lemma
  • random walks
Lecture 11 (Oct 21): small-set expanders [pdf] [one]
  • Cayley graphs, noisy hypercube, hard examples
Lecture 12 (Oct 26): electrical networks [pdf] [one]
  • effective resistance, hitting time
Lecture 13 (Oct 28): Laplacian solver [pdf] [one]
  • simple nearly linear-time algorithm
Lecture 14 (Nov 2): multiplicative weight update method [pdf] [one]
  • online experts, solving linear programs
Lecture 15 (Nov 4): maximum flow [pdf] [one]
  • electrical flow, random walk rounding
Lecture 16 (Nov 9): graph sparsification [pdf] [one]
  • Chernoff bounds, uniform sampling, randomized min-cut
Lecture 17 (Nov 11): spectral sparsification [pdf] [one]
  • effective resistance, dimension reduction, matrix Chernoff
Lecture 18 (Nov 16): linear-size spectral sparsification [pdf] [one]
  • potential functions, barrier arguments, random sampling
Lecture 19 (Nov 18): interlacing polynomials [pdf] [one]
  • probabilistic method, common interlacing
  • real stable polynomials
Lecture 20 (Nov 23): bipartite Ramanujan graphs [pdf] [one]
  • 2-lift, signed matrix
  • interlacing family, mixed characteristic polynomial
  • matching polynomial
Lecture 21 (Nov 25): Weaver's conjecture [pdf] [one]
  • multivariate barrier argument
Lecture 22 (Nov 30): strongly Rayleigh measure [pdf] [one]
  • thin tree
  • negative correlation, determinantal measure
  • generalization of MSS
  • applications to ATSP
Lecture 23 (Dec 2): local lemma [pdf] [one]
  • course review
  • local lemma, algorithmic proof