This presentation describes an emerging paradigm for the design of efficient algorithms for massive graphs. This paradigm, which we will refer to as the Laplacian Paradigm, is built on a recent suite of nearly-linear time primitives in spectral graph theory developed by Spielman and Teng, especially their solver for linear systems Ax = b, where A is the Laplacian matrix of a weighted, undirected n-vertex graph and b is an n-place vector. In the Laplacian Paradigm for solving a problem (on a massive graph), we reduce the optimization or computational problem to one or multiple linear algebraic problems that can be solved efficiently by applying the nearly-linear time Laplacian solver. So far, the Laplacian paradigm already has some successes. It has been applied to obtain nearly-linear-time algorithms for applications in semi-supervised learning, image process, web-spam detection, eigenvalue approximation, and for solving elliptic finite element systems. It has also been used to design faster algorithms for generalized lossy flow computation and for random sampling of spanning trees.

The goal of this presentation is to encourage more researchers to consider the use of the Laplacian Paradigm to develop faster algorithms for solving fundamental problems in combinatorial optimization (e.g., the computation of matchings, flows and cuts), in scientific computing (e.g., spectral approximation), in machine learning, and data analysis (such as for web-spam detection and social network analysis), and in other applications that involve massive graphs.

Biography: