About
Spectral methods have become a fundamental tool with a broad range of applications across computer science. These techniques have had a significant impact on several areas including machine learning, data mining, web search and ranking, scientific computing and computer vision. Moreover, from expander graphs and pseudorandomness, to the study of rapid mixing of Markov chains, to the use of spectral partitioning in approximation algorithms—understanding the eigenvalues and eigenvectors of the adjacency matrix (and the Laplacian) of graphs has become a standard method in every theorist’s toolkit.
Recent years have seen several exciting applications of spectral graph theory in the theory of computing. This includes work on fast solvers for linear systems, graph sparsification, local random walks, and subsequent combinatorial applications to computing maximum flows. Emerging connections between graph expansion, graph spectra and semi-definite programming hierarchies are playing a significant role in approximation algorithms and work on the Unique Games Conjecture. Newly discovered relationships between higher eigenvalues of graphs and spectral partitioning promise to create further interplay between theoretical analysis and widely employed heuristics.
This program addresses the use of spectral methods in confronting a number of fundamental open problems in the theory of computing, while at the same time exploring applications of newly developed spectral techniques to a diverse array of areas.
