"The Laplacian Paradigm: Emerging Algorithms for Massive Graphs"
Shang-Hua Teng
(University of Southern California)
Monday, March 3rd, 2014, 2:00pm
EBU3B, Room 4140
Abstract:
We discuss 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 a collection of nearly-linear-time primitives in Spectral Graph Theory developed by Spielman and Teng and its subsequent improvements by many others. The key primitive in the paradigm is a solver for a linear system, Ax = b, where A is the Laplacian matrix of a weighted graph. Other primitives include algorithms for local clustering, spectral sparsification, and low stretch spanning trees. When applying the Laplacian Paradigm, we reduce the input problem to one or multiple problems that can be efficiently solved by these spectral primitives. The Laplacian Paradigm has been used in a algorithm for computing an approximately maximum s-t flow in an undirected graph. It also been applied to obtain nearly-linear-time algorithms for applications in semi-supervised learning, image process, web-spam detection, and eigenvalue approximation.
In this talk, I will review the key elements of the Laplacian paradigm and its applications. I will also discuss two basic results inspired by this paradigm: (1) A nearly optimal, sublinear-time algorithm for identifying all nodes of significant PageRanks in a network, and (2) An extended Cheeger Inequality for a family of clusterability measures that generalizes the traditional measure of conductance, and its application to local clustering.
The talk is based on joint work with Daniel Spielman (Yale) and Paul Christiano (MIT), Jonathan Kelner (MIT), and Aleksander Madry (MIT), as well as with Christian Borgs, Michael Brautbar, Jennifer Chayes, Rumi Ghosh, and Kristina Lerman.
Speaker Bio:
Shang-Hua Teng is the Seeley G. Mudd Professor at the USC Computer Science Department, where he was a former chair (2009-2012). He received his Ph.D. degree at CMU in 1991, and taught at MIT (Math), University of Minnesota, UIUC, and Boston University. He also worked at Xerox PARC, NASA Ames, Intel, IBM Almaden, Akamai, and Microsoft Research.
Teng's main research is in theoretical computer science. He and coauthor Dan Spielman received the Gödel Prize (2008) and Fulkerson Prize (2009) for developing Smoothed Analysis. His more recent work addresses Spectral Graph Theory & the Laplacian Paradigm and its applications to maximum flows, for which he and coauthors received the best paper award at ACM STOC 2011. In addition, he has conducted research in Algorithmic Game Theory, where he and collaborators settled open questions on the complexity for computing an approximate Nash equilibrium and the complexity of market equilibria. Recently, he and collaborators developed an axiomatic framework for community identification in social and information networks, and obtained the best bound for testing the isomorphism of strongly regular graphs. Teng is also interested in mathematical board games. Kyle Burke, his former Ph.D. student, and he designed & analyzed a game called Atropos based on the beautiful, celebrated Sperner's Lemma. Teng's past research interests include parallel scientific computing, computational geometry, percolation theory, cryptography, and computer graphics, where he obtained fundamental results in geometric separators, three-dimensional Delaunay meshing, spectral graph partition, N-body simulation, and robust statistics. Teng is an ACM Fellow and Alfred P. Sloan Fellow. He has received more than ten US Patents for his work on compiler optimization, Internet technology, and social network analysis.