CS294: Graph Partitioning, Expanders and Spectral Methods
[general info]
[lecture notes] [exams and projects]
What's new
 Because of the faculty retreat, the office hours of April 21 are moved to April 20, 45pm, 625 Soda Hall
 04/19, Handout 20: Properties of expanders
 04/19, Handout 19: Expansion of random graphs
 04/02, Handout 18: MargulisGaborGalil expanders
 04/02, Handout 17: Analysis of the Zigzag graph product
 03/16, Handout 16: Expanders from the Zigzag graph product
 03/16, Handout 15: Eigenvalues and eigenvectors of Cayley graphs
 03/10, Some corrections to Handout 14
 03/08, Handout 14: ARV Analysis, part 3
 03/08, Handout 13: ARV Analysis, cont'd
 03/01, Handout 12: ARV Analysis
 03/01, Handout 11: ARV
 02/24, Handout 10: Proof of Bourgain's Theorem
 02/24, Handout 9: The sparsest cut problem
 02/21, Midterm 1 (available only to enrolled students)
 02/17, Handout 8: Spectral algorithms wrapup
 02/10. Handout 7: Higher order Cheeger inequalities, cont'd
 02/09. Handout 6: Higher order Cheeger inequalities
 02/08. Handout 5: Cheegertype inequality for λ_{n}
 02/07. Handout 4: Cheeger inequalities cont'd
 01/31. Handout 3: Cheeger inequalities
 01/31. Handout 1: introduction
 01/25. Handout 2: the basics of spectral graph theory
 01/21. Handout 0: linear algebra background
general information
Instructor: Luca
Trevisan, 625 Soda Hall, email luca at berkeley dot edu
Classes are MW, 12:30pm, in 310 Soda
Office hours: Thursdays, 23pm, 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 MarkovChain MonteCarlo algorithms, in constructing graph sparsifiers, in solving diagonallydominated 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 takehome exams and a takehome final exam.
Working on a research project related to the topics of the class can
substitute for the final exam.
References
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 MarkovChain MonteCarlo 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:

Nisheet Vishnoi
Lx=b
Foundations and Trends in Theoretical Computer Science,
Vol. 8, Nos. 12 (2012), pp 1141
Lectures
So far:
 01/20 Overview of the course. Readings: Handout 0, Handout 1
 01/25 Laplacian of a graphs and basics of spectral graph theory. Readings: Handout 2
 01/27 Normalized Laplacian of an irregular graph. Cheeger inequalities. Readings: Handout 3
 02/01 Cheeger inequalities ctd. Readings: Handout 4
 02/03 Cheegertype inequalities for λ_{n}. Readings: Handout 5
 02/08 Higherorder Cheeger inequalities. Readings: Handout 6 and these notes
 02/10 Higherorder Cheeger inequalities, cont'd. Readings: Handout 7 and these notes
 02/17 Other variants of Cheeger's inequality and the power methods. Readings: Handout 8
 02/22 The sparsest cut problem and the LeightonRao relaxation. Readings: Handout 9
 02/24 Proof of Bourgain's Theorem. Readings: Handout 10
 02/29 ARV. Readings: Handout 11
 03/02 ARV Analysis. Readings:Handout 12
 03/07 ARV Analysis, continued. Readings:Handout 13
 03/09 ARV Analysis, part 3. Readings:Handout 14
 03/14 Cayley graphs of Abelian groups: Readings: Handout 15
 03/16 Expander constructions using the ZigZag graph product: Readings: Handout 16
 03/28 Analysis of the ZigZag graph product: Readings: Handout 17
 03/30 MargulisGaborGalil Expanders: Readings: Handout 18
 04/04 Probabilistic constructions of expanders. Readings: Handout 19
 04/06 Properties of expanders. Readings: Handout 20
 04/13 Approximating counting and sampling. Readings: notes in preparation, meanwhile see Chapter 5 of Mark Jerrum's book'
 04/18 A nearly linear time algorithm for Laplacian linear equations. Readings: notes in preparation
 04/20 Solving Laplacian systems, continued. Readings: notes in preparation
 04/25 Sparsifiers. Readings: notes in preparation
 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):
 Definitions: edge and vertex expansion, uniform and general sparsest
cut problems, review of linear algebra
 Eigenvalues and expansion, Cheeger's inequality and Fiedler's spectral
partitioning algorithm
 Cheegertype inequality for Max Cut
 Higherorder Cheeger inequalities
 The power method
 Algorithms for finding sparse cuts: LeightonRao, and metric embeddings
 Bourgain's theorem (embedding of general metrics in L1)
 Algorithms for finding sparse cuts: AroraRaoVazirani
 Eigenvalues and Eigenvectors of Cayley graphs
 The ZigZag graph product construction
 The MargulisGaborGalil construction of expanders
 The expansion of random graphs
 Eigenvalues, expansion, conductance, and random walks
 Approximate counting, approximate sampling, and the MCMC method
 Counting matchings
 Electrical networks, electrical flows, and Laplacian solvers
 Graph sparsifiers
 Using electrical flows to find approximate max flows
Exams and Projects