Site menu:

Lecture notes

Notes will usually be posted the day before lecture.

Lecture 1 (May 7): introduction [pdf] [one]
  • course information and overview
  • background in linear algebra
Lecture 2 (May 9): graph spectrum [pdf] [one]
  • adjacency matrix, Laplacian matrix
  • Rayleigh quotient, Courant-Fischer
Lecture 3 (May 14): Cheeger's inequality [pdf] [one]
  • spectral partitioning algorithm
Lecture 4 (May 16): higher order Cheeger's inequality [pdf] [one]
  • spectral embedding, clustering using directions
Lecture 5 (May 21)
  • continuing on L04
Lecture 6 (May 23): improved Cheeger's inequality [pdf] [one]
  • higher-order spectral gap, k-step functions
Lecture 7 (May 28): random walks [pdf] [one]
  • mixing time
Lecture 8 (May 30): local graph partitioning [pdf] [one]
  • spectral analysis, approximation algorithm, higher eigenvalues
Lecture 9 (June 4): expander graphs [pdf] [one]
  • zig-zag product, properties, applications
Lecture 10 (June 6):
  • continuing on expander graphs
Lecture 11 (June 11): high dimensional expanders [pdf] [one]
  • simplicial complex, link expander
  • matroid complex, Oppenheim's theorem
Lecture 12 (June 13):
  • continuing on high dimensional expanders
Lecture 13 (June 18): higher order random walks [pdf] [one] (expanded on Aug 11)
  • up walk, down walk, Kaufman-Oppenheim's theorem
Lecture 14 (June 20): spectral sparsification [pdf] [one]
  • random sampling
Lecture 15 (June 25)
  • project presentations
Lecture 16 (June 27)
  • project presentations
Lecture 17 (July 4): linear-sized spectral sparsification [pdf] [one]
  • barrier function
Lecture 18 (July 9): interlacing polynomials [pdf] [one] (expanded on July 10)
  • Weaver's conjecture, probabilistic method
  • common interlacing, real-rooted and real stable polynomials
  • interlacing family, mixed characteristic polynomials
Lecture 19 (July 11)
  • continuing on interlacing polynomials (L13.pdf expanded)
Lecture 20 (July 16): bipartite Ramanujan graphs [pdf] [one]
  • 2-lift, matching polynomial
Lecture 21 (July 18): Weaver's conjecture [pdf] [one]
  • multivariate barrier functions
Lecture 22 (July 23): strongly Rayleigh measure [pdf] [one]
  • determinantal measure, random spanning trees, negative correlation
  • thin tree, probabilistic method for strongly Rayleigh measure
Lecture 23 (July 30)
  • project presentations
Lecture 24 (Aug 1)
  • project presentations