Shang-Hua Teng

Seeley G. Mudd Professor
USC Theory Group
Computer Science Department
Viterbi School of Engineering
University of Southern California

RTH 402, 941 Bloom Walk Los Angeles, CA 90089

Affiliated Research Professor of Mathematics at MIT

Ph.D. in Computer Science, Carnegie Mellon University
M.S. in Computer Science, USC
B.S. in Computer Science & B.A. in Electrical Engineering, Shanghai Jiao Tong University

I am currently teaching:

SHORT BIO:   Shang-Hua Teng is the Seeley G. Mudd Professor at the Computer Science Department, Viterbi School of Engineering, USC, where he was a former chair (2009-2012). He received a dual B.S. degree in computer science and electrical engineering from Shanghai Jiao Tong University in 1985, M.S. degree in computer science from USC in 1988, and Ph.D. degree in computer science from Carnegie Mellon University (CMU) in 1991. He was an instructor in the Department of Mathematics of MIT and professor in the Computer Science Departments of Boston University, the University of Minnesota and UIUC. He has worked and consulted for Microsoft Research, Akamai, IBM Almaden Research Center, Intel Corporation, Xerox PARC, Cray Research/SGI, Thinking Machines Corporation, and NASA Ames Research Center. He has received more than ten US Patents for his work on compiler optimization, Internet technology, and social network analysis.

Teng's main research is in algorithm design, analysis, and applications. He and coauthor Dan Spielman received the Gödel Prize (2008) and Fulkerson Prize (2009) for developing Smoothed Analysis. Recently in 2015, he and Spielman received their second Gödel Prize for their work in Laplacian Paradigm and Spectral Graph Theory. He and coauthors Paul Christiano, Jon Kelner, Aleksander Madry, and Dan Spielman received the best paper award at ACM STOC 2011 for their breakthroughs in the fundamental maximum flow/minimum cut problem. In addition, he has conducted research in Algorithmic Game Theory, where he is known for his joint paper with Xi Chen and Xiaotie Deng for resolving the complexity for computing an approximate Nash equilibrium and his joint papers on market equilibria. Teng is also interested in mathematical board games. Kyle Burke, his former Ph.D. student, and he designed & analyzed a game called Atropos, which is played on the Sperner's triangle and based on the beautiful, celebrated Sperner's Lemma. Teng's past research interests include scientific computing, Internet algorithms, computational geometry, percolation theory, compiler optimization, parallel algorithms, cryptography, computer graphics and three-dimensional mesh generation, where he had obtained fundamental results in geometric separators, well-shaped Delaunay meshing, spectral graph partition, N-body simulation, and robust statistics. Teng received the Simons Investigator Award and is an ACM Fellow, Alfred P. Sloan Fellow, winner of Senior Xerox Award for Outstanding Faculty Research (UIUC), and NSF CAREER Award.

RESEARCH:   smoothed analysis of algorithms, computational economics and game theory, spectral graph theory, mathematical board games, scientific computing, mathematical programming, combinatorial optimization, computational geometry and computer graphics.

SELECTED PUBLICATIONS:   Electrial flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs, in STOC 2011: 273-282 (with Paul Christiano, Jon Kelner, Aleksander Madry, and Daniel Spielman).

Spectral Sparsification of Graphs, in SIAM J. Computing, 40(4): 981-1025, 2011 (with Daniel Spielman).

Smoothed analysis of algorithms: the simplex algorithm usually takes polynomial number of steps, in J. ACM, 51(3) pages 385-463, May 2004 (with Daniel Spielman).

Settling the complexity of computing two-player Nash equilibria, in J. ACM, 56(3) May 2009 (with Xi Chen and Xiaotie Deng).

Separators for sphere-packings and nearest neighborhood graphs, in J. ACM, 44(1), 1-29, January 1997 (with Gary Miller, William Thurston, and Steve Vavasis).

Sliver Exudation, in J. ACM, 47(5): 883-904, 2000 (with S.-W. Cheng, T. Dey, H. Edelsbrunner, and M. Facello).

Spectral partitioning works: planar graphs and finite element meshes, in Linear Algebria and Its Applications, vol 421, 284-305, March 2007 (with Daniel Spielman).

Subspace gradient domain mesh deformation, in ACM Transactions on Graphics: SIGGRAPH'06, 1126-1134, 2006 (with Jin Huang, Xiaohan Shi, Xinguo Liu, Kun Zhou, Li-Yi Wei, Hujun Bao, Baining Guo, Harry Shum).

Atropos: A PSPACE-complete Sperner Triangle Game, in Internet Mathematics, 5(4): 477-492, 2008 (with Kyle Burke).

Learning and smoothed analysis, in FOCS 2009, 395-404 (with Adam Kalai and Alex Samorodnitsky).

Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities, in FOCS 2009, 273-282 (with Xi Chen, Decheng Dai, and Ye Du).

Smoothed analysis of multiobjective optimization, in FOCS 2009, 681-690 (with Heiko Roglin).

Higher eigenvalues of graphs, in FOCS 2009, 735-744 (with Jon Kelner, James Lee, and Greg Price).

Reducibility among fractional stability problems, in FOCS 2009, 283-292 (with Shiva Kintali, Laura Poplawski, Rajmohan Rajaraman, and Ravi Sundaram).

Finding local communities in protein networks, in BMC Bioinformatics, 10:297, 2009 (with Konstantin Voevodski and Yu Xia).

k-nearst neighbor clustering and percolation theory, in Algorithmica, 49(3):192-211, 2007 (with Frances Yao).

Security, verifiability, and universality in distributed computing, in J. Algorithms 11(3):492-521, 1990 (with Ming-Deh Huang).

Functional inversion and communication complexity, in Journal Cryptology, 7(3):153-170, 1994.

Provably good partitioning and load balancing algorithms for parallel adaptive N-Body simulation, in SIAM J, Scientific Computing, 19:635-654, 1998.

TEACHING:   • algorithms • cryptography and computer security • linear algebra for computer science • algorithms for the new age: games, economics, networking, and data analysis • scientific computing • numerical analysis • spectral graph theory • probabilistic methods

INDUSTRY/INVENTION:   Software: mesh partitioning (Xerox/MathWorks), transistor-level circuit simulation (Intel), web crawling (IBM), massive data analysis (Akamai)

Patents: more than 10 patents in compiler methods and Internet technologies


PERSONAL:   I love Latin music and Latin dance, especially Salsa Dancing. I also like cooking, reading, and traveling, and enjoy solving math problems on the airplane.

CONTACT:   shanghua AT usc DOT edu

TEACHING:   CSCI 670: Advanced Analysis of Algorithms (Fall 2013)  
    CSCI 499: Cryptography - Fundamentals of Secure Communication & Computation (Fall 2013)  
    CSCI 670: Advanced Analysis of Algorithms (Spring 2012)  
    CSCI 599: Algorithms for the New Age: Games, Economics, Networking, & Data Analysis (Fall 2010)  
    CSCI 303: Analysis of Algorithms (Spring 2010)  
RECENT TALKS:   Algorithmic Primitives for Network Analysis: Through the Lens of the Laplacian Paradigm SIAM Data Mining Conference, 2012  

CV, Research Statements, Teaching Statements, Career Narrative, Biographical Sketch