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, 4-5pm, 625 Soda Hall
- 04/19, Handout 20: Properties of expanders
- 04/19, Handout 19: Expansion of random graphs
- 04/02, Handout 18: Margulis-Gabor-Galil expanders
- 04/02, Handout 17: Analysis of the Zig-zag graph product
- 03/16, Handout 16: Expanders from the Zig-zag 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 wrap-up
- 02/10. Handout 7: Higher order Cheeger inequalities, cont'd
- 02/09. Handout 6: Higher order Cheeger inequalities
- 02/08. Handout 5: Cheeger-type 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, 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.
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 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:
-
Nisheet Vishnoi
Lx=b
Foundations and Trends in Theoretical Computer Science,
Vol. 8, Nos. 1-2 (2012), pp 1-141
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 Cheeger-type inequalities for λn. Readings: Handout 5
- 02/08 Higher-order Cheeger inequalities. Readings: Handout 6 and these notes
- 02/10 Higher-order 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 Leighton-Rao 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 Zig-Zag graph product: Readings: Handout 16
- 03/28 Analysis of the Zig-Zag graph product: Readings: Handout 17
- 03/30 Margulis-Gabor-Galil 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
- Cheeger-type inequality for Max Cut
- Higher-order Cheeger inequalities
- The power method
- Algorithms for finding sparse cuts: Leighton-Rao, and metric embeddings
- Bourgain's theorem (embedding of general metrics in L1)
- Algorithms for finding sparse cuts: Arora-Rao-Vazirani
- Eigenvalues and Eigenvectors of Cayley graphs
- The Zig-Zag graph product construction
- The Margulis-Gabor-Galil 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