Site menu:

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.

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.