The Laplacian Paradigm: Emerging Algorithms for Massive Graphs
Abstract
The speaker will present an emerging paradigm, called the Laplacian Paradigm, for the design of efficient algorithms for massive graphs. This paradigm is built on a recent suite of nearly-linear time primitives in spectral graph theory developed by the speaker and Prof Daniel Spielman from Yale University, especially their solver for linear systems Ax = b, where A is the Laplacian matrix of a weighted, undirected graph. In the Laplacian Paradigm for solving a problem, they reduce the computational problem to one or multiple linear algebraic problems that can be solved efficiently by the Laplacian solver. So far, the Laplacian paradigm already has some successes in semi-supervised learning, image process, web-spam detection, eigenvalue approximation, and finite element computations. It has also been used to design faster algorithms for generalized lossy flows, maximum flows, 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, scientific computing, machine learning, data analysis (i.e., social network analysis), and in other applications that involve massive graphs.
About the Speaker
Prof. Teng Shang-Hua is the Seeley G. Mudd Professor and the Chairman of the Computer Science Department at the Viterbi School of Engineering of University of Southern California. He taught as a faculty in the Department of Mathematics of MIT and in the Computer Science Departments of Boston University, the University of Minnesota and University of Illinois at Urbana-Champaign. He has worked and consulted for Microsoft Research, Akamai, IBM Almaden Research Center, Intel Corporation, Xerox PARC, Cray Research/SGI, Thinking Machine Corporation, and NASA Ames Research Center. He received a dual BS degree in computer science and in electrical engineering from Shanghai Jiao Tong University in 1985, a MS degree in computer science from University of Southern California in 1988, and a PhD degree in computer science from Carnegie Mellon University in 1991.
Prof. Teng is a recipient of the 2009 Fulkerson Prize (AMS-MPS) and the 2008 Gödel Prize (ACM-EATCS) for his joint work on Smoothed Analysis of Algorithms with Prof Daniel Spielman. He is also an ACM Fellow, Alfred P. Sloan Fellow, and has received NSF Faculty Early Career Development Award. His recent research interests include computational game and economics theory, spectral graph theory, scientific computing, and mathematical programming. He has received more than ten US Patents for his work on compiler optimization and Internet technology.
