CS 798 - Algorithmic Spectral Graph Theory

CS 798: Algorithmic Spectral Graph Theory

Lecture:	Mondays and Wednesdays, 1:30-2:50, DC 2568.
Instructor:	Lap Chi Lau
Office hours:	Mondays and Tuesdays, 3-4, DC 3120.
Tutor:	Tsz Chiu Kwok

In this course, we will study how eigenvalues and eigenvectors of matrices can be used to design and analyze algorithms for graph problems. We will cover topics including graph partitioning, random walks, electrical networks, solving linear equations, and graph sparsification. We will see how these ideas can be applied to make progress on fundamental problems including the unique games conjecture, the maximum flow problem, the 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.
small-set expansion.
expanders, zig-zag product, small-set expanders.
electrical networks.
Laplacian equations solver, maximum flow.
graph sparsification, concentration bounds.
spectral sparsification, effective resistance.
linear-sized sparsifiers, barrier argument.
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 spectral algorithms to get some ideas 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.
Sparse Approximations, by Nick Harvey.

Site menu: