CS359G: Graph Partitioning and Expanders
[general info]
[lecture notes] [coursework]
general information
Instructor: Luca
Trevisan, Gates 474, Tel. 650 723-8879, email trevisan at stanford dot edu
Classes are Tuesday-Thursday, 2:15-3:30pm, location TBA
Office hours: TBA
About the course
The mathematics of expander graphs is studied by three distinct
communities:
- The algorithmic problem of finding a small balanced cut
in a graph (that is, of finding a certificate that a graph is *not* an
expander) is a fundamental problem in the area of approximation
algorithms, and good algorithms for it have many applications, from
doing image segmentation to driving divide-and-conquer procedures.
-
Explicit constructions of highly expanding graphs have many applications
in algorithms, data structures, derandomization and cryptography; many
constructions are algebraic, and lead to deep questions in group theory,
but certain new constructions are purely combinatorial.
- The speed of
convergence of MCMC (Markov-Chain Monte-Carlo) algorithms is related to
the expansion of certain exponentially big graphs, and so the analysis
of such algorithms hinges on the ability to bound the expansion of such
graphs.
In this course we aim to present key results from these three areas, and
to explore the common mathematical background.
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. 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.
Lectures
The following is a tentative schedule:
- Definitions: edge and vertex expansion, uniform and general sparsest
cut problems, review of linear algebra
- Eigenvalues and expansion, Cheeger's inequality and the spectral
partitioning algorithm
- Cheeger's inequality, continued
- Classes of graphs for which spectral partitioning is provably good
- Eigenvalues, expansion, conductance, and random walks
- Applications of expanders: derandomization
- Applications of expanders: security amplification of one-way permutations
- The Margulis-Gabor-Galil construction of expanders
- The Zig-Zag graph product construction
- Algorithms for finding sparse cuts: Leighton-Rao, and metric embeddings
- Equivalence of rounding the Leighton-Rao relaxation and
embedding general metrics into L1
- Algorithms for finding sparse cuts: Arora-Rao-Vazirani
- Arora-Rao-Vazirani, continued
- Integrality gaps for the Arora-Rao-Vazirani relaxation
- Approximate counting, approximate sampling, and the MCMC method
- Random Spanning trees
- Counting colorings in bounded-degree graphs
- Counting perfect matchings in dense bipartite graphs
- The Metropolis algorithm