Our agenda for the next few weeks looks something like this:

  1. The discrete Cheeger inequality
  2. The connection between {\lambda_2} and the mixing time of random walks
  3. Planar separators, eigenvalues, and circle packings
  4. Expander graphs and rapid mixing
  5. The small-set expansion problem and the Unique Games Conjecture
  6. Higher-order Cheeger inequalities
  7. Cheeger inequalities for very large eigenvalues (Arora-Barak-Steurer)
  8. Mixing times and the spectral profile


This is the course web site for CSE 599S: Algorithmic Spectral Graph Theory. This is where notes, homeworks, and video will be posted.

The class will be held every Monday and Wednesday, from 3-4:20pm in CSE 305.