Events Calendar

CAMS Colloquium: Shang-Hua Teng (USC) - Through the Lens of the Laplacian Paradigm: Big Data and Scalable Algorithms -- a Pragmatic Match Made On Earth

Speaker: Shang-Hua Teng, USC

Talk Title: Through the Lens of the Laplacian Paradigm: Big Data and Scalable Algorithms -- a Pragmatic Match Made On Earth

Abstract: In the age of Big Data, efficient algorithms are in higher demand now more than ever before. While Big Data takes us into the asymptotic world envisioned by our pioneers, the explosive growth of problem size has also significantly challenged the classical notion of efficient algorithms:

Algorithms that used to be considered efficient, according to polynomial-time characterization, may no longer be adequate for solving today's problems. It is not just desirable, but essential, that efficient algorithms should be scalable. In other words, their complexity should be nearly linear or sub-linear with respect to the problem size. Thus, scalability, not just polynomial-time computability, should be elevated as the central complexity notion for characterizing efficient computation.

In this talk, I will discuss the emerging Laplacian Paradigm, which has led to breakthroughs in scalable algorithms for several fundamental problems in network analysis, machine learning, and scientific computing. I will focus on three recent applications: (1) PageRank Approximation (and identification of network nodes with significant PageRanks). (2) Random-Walk Sparsification. (3) Scalable Newton's Method for Gaussian Sampling.

Biography: Dr. Shang-Hua Teng has twice won the prestigious Godel Prize in theoretical computer science, first in 2008, for developing the theory of smoothed analysis , and then in 2015, for designing the groundbreaking nearly-linear time Laplacian solver for network systems. Both are joint work with Dan Spielman of Yale --- his long-time collaborator. Smoothed analysis is fundamental for modeling and analyzing practical algorithms, and the Laplacian paradigm has since led to several breakthroughs in network analysis, matrix computation, and optimization. Citing him as, "one of the most original theoretical computer scientists in the world", the Simons Foundation named Teng a 2014 Simons Investigator, for pursuing long-term curiosity-driven fundamental research. He and his collaborators also received the best paper award at ACM Symposium on Theory of Computing (STOC) for what's considered to be the "first improvement in 10 years" of a fundamental optimization problem --- the computation of maximum flows and minimum cuts in a network. In addition, he is known for his joint work with Xi Chen and Xiaotie Deng that characterized the complexity for computing an approximate Nash equilibrium in game theory, and his joint papers on market equilibria in computational economics. He and his collaborators also pioneered the development of well-shaped Dalaunay meshing algorithms for arbitrary three-dimensional geometric domains, which settled a long-term open problem in numerical simulation, also a fundamental problem in computer graphics. Software based on this development was used at the University of Illinois for the simulation of advanced rockets. Teng is also interested in mathematical board games. With his former Ph.D. student Kyle Burke, he designed and analyzed a game called Atropos , which is played on the Sperner's triangle and based on the beautiful, celebrated Sperner's Lemma. In 2000 at UIUC, Teng was named on the List of Teachers Ranked as Excellent by Their Students for his class, "Network Security and Cryptography". He has worked and consulted for Microsoft Research, Akamai, IBM Almaden Research Center, Intel Corporation, Xerox PARC, and NASA Ames Research Center, for which he received fifteen patents for his work on compiler optimization, Internet technology, and social network.

Host: USC CAMS

Location: Kaprielian Hall (KAP) - 414

Audiences: Everyone Is Invited

Contact: Assistant to CS chair