| SHORT BIO |
|
Dr. Shang-Hua Teng has twice won the prestigious
Gödel 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.
His manuscript,
Scalable Algorithms for
Data and Network Analysis,
received Phi Kappa Phi Faculty Recognition Award in 2020.
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.
For professional leadership, he served as the chair of the USC
Computer Science Department (2009 - 2012). He is the current chair of the Steering Committee for ACM-SIAM Symposium on Discrete Algorithms (SODA) and Vice Chair of IEEE Technical Committee on Mathematical Foundations of Computing. He was also the 2018 chair of the ACM Donald E. Knuth Prize Committee.
Currently, he is on the Advisory Board of the USC Women in Science and
Engineering (WiSE) and the Board of Directors of
USC Center for Applied Mathematical Sciences.
...
Click here , for full career narrative.
|
| SELECTED PUBLICATIONS: |
|
Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography
(with Kyle Burke and Matthew Ferland), FOCS, 2021
Quantum-Inspired Combinatorial Games:
Structures and Computational Complexity,
(with Kyle Burke and Matthew Ferland), FUN, 2020
Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis (ACM-SIAM SODA)
(with Jiaqing Jiang, Xiaoming Sun, Bujiao Wu, Kewen Wu, and Jialin Zhang), 2020
On the Equivalence Between High-Order Network-Influence Frameworks (with Wei Chen and Hanrui Zhang), 2020
Scalable Algorithms for
Data and Network Analysis,
Foundations and Trend in Theoretical Computer Science, 2016
An Axiomatic Approach to Community Detection,
Innovations in Theoretical Computer Science (ITCS 2016)
(with Christian Borgs, Jennifer Chayes, and Adrian Marple)
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).
Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric,
Diagonally Dominant Linear Systems, Journal on Matrix Analysis (2014)
35 (3) (with Dan Spielman)
Spectral Sparsification of Graphs, in SIAM J. Computing,
40(4): 981-1025, 2011 (with Daniel Spielman).
A Local Clustering Algorithm for Massive Graphs and
Its Application to Nearly Linear Time Graph Partitioning, SIAM J. Comput.
42(1): 1-26 (2013) (with Dan Spielman)
Settling the complexity of computing two-player Nash equilibria, in J. ACM, 56(3) May 2009 (with Xi Chen and Xiaotie Deng).
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).
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.
|
|
