Site menu:

Lecture notes

Notes will usually be posted the day before lecture. The latex template is created by John Watrous.

Notes [pdf]
Chapter 1 (Jan 6): Overview [pdf]
Chapter 2 (Jan 6): Linear Algebra [pdf] (last updated: Jan 23)
  • eigenvalues and eigenvectors
  • formulas and inequalities
Chapter 3 (Jan 11): Graph Spectrum [pdf]
  • adjacency matrix, bipartiteness
  • Laplacian matrix, connectedness
Chapter 4 (Jan 11,13): Cheeger's Inequality [pdf]
  • spectral partitioning algorithm
Chapter 5 (Jan 18): Generalizations of Cheeger's Inequality [pdf]
  • bipartiteness, small-set expansion
  • higher-order and improved Cheeger inequalities
Chapter 6 (Jan 20): Random Walks [pdf] (last updated: Jan 23)
  • fundamental theorem, mixing time
Chapter 7 (Jan 25,27): Expander Graphs [pdf]
  • properties: expander mixing lemma, random walks, etc.
  • constructions: zig-zag product
  • applications: expander codes, probability amplication, log-space connectivity, etc.
Chapter 8 (Feb 1): Fastest Mixing and Vertex Expansion [pdf]
  • Cheeger inequality for vertex expansion
Chapter 9 (Feb 3): Spectral Sparsification [pdf]
  • random sampling algorithms
Chapter 10 (Feb 8): Barrier Method [pdf]
  • linear-sized spectral sparsification
Chapter 11 (Feb 10): Spectral Rounding [pdf]
  • experimental and network design, polynomial approach
Chapter 12 (Feb 15): Method of Interlacing Polynomials [pdf]
  • interlacing family, restricted invertibility
Chapter 13 (Feb 17): Real-Stable Polynomials [pdf]
  • stability preserving operations, multilinear formula and interlacing family
Chapter 14 (Mar 1): Bipartite Ramanujan Graphs [pdf]
  • 2-lift, matching polynomials
Chapter 15 (Mar 3): Multivariate Barrier Method [pdf]
  • Weaver's conjecture, probabilistic formulation
Chapter 16 (Mar 8): Strongly Rayleigh Measure [pdf]
  • determinantal measure, negative correlation
Chapter 17 (Mar 10): More Interlacing Families [pdf]
  • strongly Rayleigh measure, thin tree
  • matrix discrepancy, spectral rounding
  • higher rank matrices
Chapter 18 (Mar 15): Real Stability and Log Concavity [pdf]
  • Gurvits capacity inequality, approximating permanent
  • log-concavity, determinant maximization
Chapter 19 (Mar 17): High Dimensional Expanders [pdf]
  • simplicial complexes, local spectral expanders
  • Oppenheim's trickling down theorem, matroid complexes
Chapter 20 (Mar 22): Higher Order Random Walks [pdf]
  • bipartite graphs, up-down walks, down-up walks
  • Kaufman-Oppenheim theorem, matroid expansion conjecture
Chapter 21 (Mar 24): Spectral Independence [pdf]
  • improved analysis, correlation matrix, applications
Chapter 22 (Mar 29): Log-Concave Polynomials [pdf]
  • strongly log-concavity, sector real-stability, fractionally log-concavity
Chapter 23 (Mar 31): Log-Sobolev Inequalities [pdf]
  • log-Sobolev constants, mixing time, strongly log-concave distributions
Chapter 24 (Apr 5): Entropic Independence [pdf]
  • local entropy contraction, fractional log-concavity, global entropy contraction