Algebraic Graph Algorithms: The Laplacian and Beyond

This project will exploit algebraic properties of operators associated with graphs in an integrated set of research and educational activities designed to develop new mathematical and algorithmic techniques; apply these to the solution of real-world problems and longstanding theoretical questions in mathematics, computer science, biology, and physics; and make these techniques broadly known and accessible to students, researchers, and practitioners in many fields.

This research has its origins in spectral graph theory, which studies how the eigenvalues and eigenvectors of the graph Laplacian (and other related matrices) interact with the combinatorial structure of the graph. Spectral graph theory has been one of the great success stories in both the theory and practice of algorithm design. It has led to fundamental advances in graph partitioning, web search (notably including Google's PageRank algorithm), the understanding of random processes and the algorithms derived from them, the construction of error correcting codes, derandomization, convex optimization, machine learning, and many others.

While the eigenvalues and eigenvectors of the Laplacian capture a striking amount of the structure of the graph, they certainly do not capture all of it. Recent work by the principal investigators and other researchers suggests that theoretical computer scientists have only scratched the surface of what can be done if they are willing to broaden their investigation, extending it to study more general algebraic properties of the Laplacian than just its eigenvalue structure, and more general operators than just the Laplacian.

Under this award, the principal investigators will build a research program across the three universities involved in this proposal to develop such a theory and its applications. This initiative has the potential to provide transformative advances in a range of theoretical and applied areas of computer science, including:

(*) Faster algorithms for fundamental graph problems, such as Maximum Flow, Minimum Cut, Minimum Cost Flow, Multicommodity Flow, approximating Sparsest Cut, generating random spanning trees, and constructing low-stretch spaning trees.

(*) Better algorithms for the analysis of data, with potential applications to the Unique Games Conjecture.

(*) Faster algorithms for solving broad classes of important linear systems, both sequentially and in parallel.

(*) Faster distributed algorithms for information dissemination in networks.

(*) A spectral and algebraic graph theory for directed graphs, based on ideas from differential geometry.

(*) Novel quantum algorithms for a large class of problems that appear to be hard for classical computers.

(*) New techniques for problems in Quantum Physics based on ideas developed in Computer Science and Combinatorics.

The principal investigators will also work to disseminate these techniques by developing courses, training undergraduate and graduate students, and introducing these ideas to scientists in other fields.