ICERM Workshop: Electrical Flows, Graph Laplacians, and Algorithms: Spectral Graph Theory and Beyond
Month: April 2014
Date: April 7--11
Name: ICERM Workshop: Electrical Flows, Graph Laplacians, and Algorithms: Spectral Graph Theory and Beyond
Location: ICERM, Providence, Rhode Island.
Spectral graph theory, which studies how the eigenvalues and eigenvectors of the graph Laplacian and other related matrices interact with the combinatorial structure of a graph, is a classical tool in both the theory and practice of algorithm design. The success of this approach has been rooted in the efficiency with which eigenvalues and eigenvectors can be computed and in the large number of ways that a graph's properties are connected to the Laplacian's spectrum, particularly to the value of its second smallest eigenvalue $\lambda 2$. While the eigenvalues and eigenvectors of the Laplacian capture a striking amount of the structure of the graph, they do not capture it all. Recent work suggests that we have only scratched the surface of what can be done if we are to broaden our investigation to include more general linear-algebraic properties of the matrices we associate to graphs. The workshop will bring researchers together to study and advance this emerging frontier in algorithmic graph theory.