Site menu:

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:

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.

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.