Files in This Item:
File Format
b1126642.mp4Streaming VideoView/Open
Title: The Laplacian Paradigm: Emerging Algorithms for Massive Graphs
Originating Office: IAS
Speaker: Teng, Shang-Hua
Issue Date: 24-Nov-2010
Event Date: 24-Nov-2010
Group/Series/Folder: Record Group 8.15 - Institute for Advanced Study
Series 3 - Audio-visual Materials
Location: 8.15:3 box 1.5
Notes: IAS Distinguished Lecture.
Abstract: Prof Teng presents 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.
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 has received more than ten US Patents for his work on compiler optimization and Internet technology.
Duration: 85 min.
Appears in Series:8.15:3 - Audio-visual Materials
Videos for Public -- Distinguished Lectures