Shang-Hua Teng

Chair, Computer Science Department
Seeley G. Mudd Professor
Viterbi School of Engineering
University of Southern California

Affiliated Research Professor of Mathematics at MIT

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.

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

• ACM STOC Best Paper (2011) -- for developing new maximum flows/minimum cuts algorithms
• Fulkerson Prize by American Mathematical Society and Mathematical Programming Society (2009) -- for establishing the polynomial smoothed complexity of the simplex algorithm
• ACM fellow (2009) -- for contributions to theoretical computer science, algorithms and interdisciplinary applications of computing
• ISAAC Best Paper (2009) -- for establishing the computational equivalence of Fisher and Arrow-Debreu market equilibria
• Gödel Prize by ACM/European Association for Theoretical Computer Science (2008) -- for developing the smoothed analysis framework and for predicting the performance of optimization tools on real data
• List of Teachers Ranked as Excellent by Their Students at UIUC (2000) -- for teaching the "Network Security and Cryotography" class
• Senior Xerox Award for Outstanding Faculty Research at UIUC (1999) -- for developing the first well-shaped three-dimensional Delaunay meshing algorithm
• IBM Faculty Development Award (1998) -- for algorithmic/software development in collaborative Web crawling for information gathering/processing over Internet
• Sloan Fellow (1996) -- for showing spectral partitioning works for planar graphs and finite-element meshes
• NSF CAREER (1995) -- "Geometric Methods for Numerical Computing"