Applied Mathematics Colloquium

Monday April 2, 2012 4:15 PM

The Laplacian Paradigm: Emerging Algorithms for Massive Graphs

Speaker: Shanghua Teng, Department of Computer Science, USC
Location: Annenberg 105
In Computer Science and Applied Mathematics, we often represent a graph by its adjacency matrix. This linear algebraic view of graphs can be very useful. For example, it has facilitated the design of the fast algorithm for the shortest path problem, the introduction of PageRank, and the development of spectral graph theory.

In this talk, I focus on the Laplacian matrix, a simple modification of the adjacency matrix. The Laplacian matrix had been extensively used for partitioning graphs that arise in VLSI design and high-performance computing. As the starting point of our discussion, I will show that every Laplacian matrix can be inverted efficiently, that is, the linear system Ax = b, where A is the Laplacian matrix, can be solved in nearly linear time. I then describe an emerging paradigm, which we refer to as the Laplacian Paradigm, for the design of efficient algorithms for massive graphs. This paradigm is built on the nearly-linear time Laplacian solver as well as a few other algorithms (such as for local clustering, graph sparsification, and high quality spanning trees) developed for supporting this solver.

I will discuss some recent progress in applying the Laplacian paradigm. Our first example will be the nearly linear time solution to a problem that we all learned in high school, that is, to determine the electrical flows in a circuit of resistors. We then show by solving a sequence of electrical flow problems we obtain the fastest algorithm for computing an approximate maximum s-t flow in an undirected graph. Recently, significant improvements have been made to the Laplacian solver and practical implementation might become available in the near future.

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, scientific computing, machine learning, network analysis, and other applications that involve massive graphs.

Joint work with Daniel Spielman (Yale) and Paul Christiano (MIT), Jonathan Kelner (MIT), and Aleksander Madry (MIT).
Series Applied Mathematics Colloquium Series

Contact: Sydney Garstang at x4555
For more information visit: