CS294: Graph Partitioning, Expanders and Spectral Methods

[general info]  [lecture notes] [exams and projects]

What's new

general information

Instructor: Luca Trevisan, 625 Soda Hall, email luca at berkeley dot edu

Classes are MW, 1-2:30pm, in 310 Soda

Office hours: Thursdays, 2-3pm, in 625 Soda

About the course

This course is about applications of linear algebra to graph theory and to graph algorithms. We will be interested in spectral algorithms for finding graph cuts and clusters, in the construction of expanders, in the analysis of Markov-Chain Monte-Carlo algorithms, in constructing graph sparsifiers, in solving diagonally-dominated systems of linear equations, in using such solutions to compute electrical flows, and in using electrical flows to approximate the max flow problem.

Prerequisites: a basic course in linear algebra and a course on algorithms; preferably, also a basic understanding of linear programming and of duality.

Assignments: two midterm take-home exams and a take-home final exam. Working on a research project related to the topics of the class can substitute for the final exam.


The main reference will be a set of lecture notes. Notes will be posted after each lecture. (Here are some older notes.) In addition, the following texts will be helpful references.

On sparsest cut approximation algorithms:

On spectral graph theory and on explicit constructions of expander graphs: On Markov-Chain Monte-Carlo algorithms for uniform generation and approximate counting:

On solving systems of Laplacian equations, and on the theory of electrical networks and of electrical flows, and the applications to max flow:


So far:
  1. 01/20 Overview of the course. Readings: Handout 0, Handout 1
  2. 01/25 Laplacian of a graphs and basics of spectral graph theory. Readings: Handout 2
  3. 01/27 Normalized Laplacian of an irregular graph. Cheeger inequalities. Readings: Handout 3
  4. 02/01 Cheeger inequalities ctd. Readings: Handout 4
  5. 02/03 Cheeger-type inequalities for λn. Readings: Handout 5
  6. 02/08 Higher-order Cheeger inequalities. Readings: Handout 6 and these notes
  7. 02/10 Higher-order Cheeger inequalities, cont'd. Readings: Handout 7 and these notes
  8. 02/17 Other variants of Cheeger's inequality and the power methods. Readings: Handout 8
  9. 02/22 The sparsest cut problem and the Leighton-Rao relaxation. Readings: Handout 9
  10. 02/24 Proof of Bourgain's Theorem. Readings: Handout 10
  11. 02/29 ARV. Readings: Handout 11
  12. 03/02 ARV Analysis. Readings:Handout 12
  13. 03/07 ARV Analysis, continued. Readings:Handout 13
  14. 03/09 ARV Analysis, part 3. Readings:Handout 14
  15. 03/14 Cayley graphs of Abelian groups: Readings: Handout 15
  16. 03/16 Expander constructions using the Zig-Zag graph product: Readings: Handout 16
  17. 03/28 Analysis of the Zig-Zag graph product: Readings: Handout 17
  18. 03/30 Margulis-Gabor-Galil Expanders: Readings: Handout 18
  19. 04/04 Probabilistic constructions of expanders. Readings: Handout 19
  20. 04/06 Properties of expanders. Readings: Handout 20
  21. 04/13 Approximating counting and sampling. Readings: notes in preparation, meanwhile see Chapter 5 of Mark Jerrum's book'
  22. 04/18 A nearly linear time algorithm for Laplacian linear equations. Readings: notes in preparation
  23. 04/20 Solving Laplacian systems, continued. Readings: notes in preparation
  24. 04/25 Sparsifiers. Readings: notes in preparation
  25. 04/27 Computing effective resistances, and a sketch of max flow algorithms. Readings: notes in preparation
The following is a tentative syllabus (some topics will span multiple lectures):

Exams and Projects