CS229r: Spectral Graph Theory in Computer Science





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.