CS 860 - Spectral Graph Theory

CS 860: Spectral Graph Theory

Lecture:	Tuesdays and Thursdays, 11:00-12:20, DC 2568.
Instructor:	Lap Chi Lau
Office hours:	Thursdays, 1:30-2:30, DC 3120.
Piazza page:	piazza.com/uwaterloo.ca/spring2019/cs860

This is a research-oriented graduate course in spectral graph theory. In this course, we will study how eigenvalues and eigenvectors of matrices can be used to design and analyze algorithms for combinatorial problems. We will cover topics including graph partitioning, random walks, high dimensional expanders, electrical networks, graph sparsification, and polynomial methods. We will see how these ideas can be applied to make progress on fundamental problems including the matroid expansion conjecture, Kadison-Singer problem, and the traveling salesman problem. The following is a tentative syllabus.

eigenvalues, eigenvectors, Laplacian matrices.
second eigenvalue, Cheeger's inequality, spectral partitioning.
higher eigenvalues, generalizations of Cheeger's inequality.
random walks, mixing time, local graph partitioning.
expanders, zig-zag product, small-set expanders.
simplicial complex, high dimensional expanders.
higher order random walks, matroid expansion conjecture.
electrical networks, spectral sparsification, effective resistance.
linear-sized sparsifiers, barrier method.
interlacing polynomials, real-stable polynomials.
bipartite Ramanujan graphs.
Kadison-Singer problem.
spectrally thin tree, ATSP.

References: Notes will be provided. See my previous notes on CS 798 to have a good idea of the topics to come, but I will add some new material and change the presentation of some old material. See also the project page for further references. Below are some similar courses in other universities for your references.

Spectral Graph Theory, by Dan Spielman.
Graph Partitioning and Expanders, by Luca Trevisan.
Recent Developments in Approximation Algorithms, by Shayan Oveis Gharan.
High dimensional expanders, by Irit Dinur.

Site menu: