CS229r: Spectral Graph Theory in Computer Science

Semester: 

Fall

Offered: 

2020

Spectral graph theory is about how eigenvalues, eigenvectors, and other linear-algebraic quantities give us useful information about a graph, for example about how well-connected it is, how well we can cluster or color the nodes, and how quickly random walks converge to a limiting distribution.  Spectral graph theory has turned out to be extremely useful in theoretical computer science, with applications ranging from solving linear systems, converting randomized algorithms to deterministic algorithms, sampling via Markov Chain Monte Carlo, counting, web search, and maximum flow.  In this course, we will study both the mathematics and the algorithmic applications of spectral graph theory, including some results from the past couple of years.  Along the way, we will cover a number of concepts and tools that are quite broadly useful, such as mixing of Markov chains, expander graphs, algorithmic linear algebra, and the multiplicative weights method for optimization. 

Announcements

  • Future course announcements will be made on the course Piazza site.
  • If you are planning to audit the course but not formally register, please email TF Chi-Ning Chou <chiningchou@g.harvard.edu> so that you can be added to the Piazza and Perusall sites.
  • There is a review section on Wednesday 9/2 at 10:30am Eastern time.  See Piazza for the zoom link.
  • Our first regular class meeting is Thursday 9/3 at 1:30pm Eastern time.  See Piazza for the zoom link.
  • A link to the recording of our live shopping period session on 8/20 is available on Piazza, and a copy of the whiteboard is available on the course schedule below.
  • See the course schedule below for Problem Set 0, which you can use to gauge your preparation for the course.  Pointers for linear algebra background can be found in the Spielman text listed in the syllabus, and posted on Perusall.

Links