
Speaker Shanghua Teng Affiliation USC Host Madhu Sudan Duration 01:06:24 Date recorded 27 July 2011 We describe 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 nearlylinear 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 nvertex graph and b is an nplace vector. In the Laplacian Paradigm for solving a problem, we reduce the optimization or computational problem to one or multiple linear algebraic problems that can be solved efficiently by applying the nearlylinear time Laplacian solver and the algorithms in this suite for local clustering, spectral sparsification, and low stretch spanning trees. The Laplacian Paradigm has been used in a recent algorithm for computing an approximately maximum st flow in a capacitated, undirected graph. It has also been applied to obtain nearlylineartime algorithms for applications in semisupervised learning, image process, webspam detection, eigenvalue approximation, and for solving elliptic finite element systems. Recently, almost all original primitives in this suite including the Laplacian solver itself have been significantly improved 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, scientiļ¬c computing, machine learning, network analysis, and other applications that involve massive graphs. NOTE: Considering the recent colloquium talks by Dan Spielman and Jon Kelner on spectral graph sparsification, maximum flow computation, improved Laplacian linear solver, and application of Laplacian Paradigm to machine learning, respectively, I will focus technically on the local clustering algorithms in the context of motivating the Laplacian Paradigm. Joint work with Daniel Spielman (Yale) and Paul Christiano (MIT), Jonathan Kelner (MIT), and Aleksander Madry (MIT).
©2011 Microsoft Corporation. All rights reserved.
