Shang-Hua Teng

Professor of Computer Science at Boston University
Senior Research Scientist at Akamai Technologies Inc.
Affiliated Research Professor of Mathematics at MIT

Ph.D. in Computer Science, Carnegie Mellon University

Also worked or taught at Xerox PARC, MIT, NASA Ames Research Center, Intel, the University of Minnesota, IBM Almadan Research Center, and University of Illinois at Urbana-Champaign, Tsinghua, Microsoft Research, Microsoft Research Asia, and Microsoft Research New England.

Email: steng AT cs DOT bu DOT edu

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


Algorithmic Game Theory and its Economics Applications


MAIN:   Smoothed Analysis of Algorithms and Heuristics, Spectral Graph Theory, Computational Game Theory, Combinatorial Scientific Computing, Combinatorial Optimization, Mathematical Programming, Parallel Scientific Computing, Graph Partitioning and Data Mining, Computational Geometry with Applications in Computer Graphics and Mesh Generation, Graph Embedding.

SECONDARY:   Cryptography and Computer Security, Internet Algorithms and Software, On-line Scheduling, VLSI and Circuit Simulation, Large-scale Information Processing and Organization, Compiler Optimization, String Matching, Regression and Robust Statistics, Percolation and Phase Transition, and Bioinformatics.

OVERALL:   I like interdisciplinary research and studies that intersect both theory and applications. Although these topics above appear to be diverse, the underlying principle of my research has been the same, that is, to understand the mathematical structure of these problems in order to design efficient algorithms and software.


Algorithm Analysis, Complexity, and Mathematical Programming: Developed the theory of Smoothed Analysis to explain why some algorithms and heuristics work well in practice in spite of having poor worst-case complexity. Proved that the smoothed time complexity of the simplex method for linear programming is polynomial despite its exponential worst-case complexity. This work was quoted as one of the three significant accomplishments funded by the computer science division of the NSF in National Science Fundation Summary of FY 2003 Budget Request to Congress and covered in Technology Review, by Megan Vandre. (With Dan Spielman).

Computational Game Theory: Solved a major open question in Computational Game Theory by showing that the problems of finding a Nash equilibrium of a two-player game and of finding a market equilibrium of a Leontief economy DO NOT have a fully polynomial-time approximation scheme, unless PPAD is in P. Furthermore, proved that the smoothed complexity of the classic Lemke-Howson algorithm for game equilibria and Scarf's algorithm for fixed points and market equilibria is not polynomial unless PPAD is in RP. (With Xi Chen and Xiaotie Deng; Li-Sha Huang; and Paul Valiant).

Nearly-Linear Time Graph Algorithms: Developed the first nearly linear-time algorithm for spectral partitioning, graph sparsification, and local clustering. (With Dan Spielman). Proved that every weighted connected graph has a subgraph spanning tree of average stretch O(log2 n loglog n) and developed a nearly linear-time algorithm for construting the low-stretch spanning tree. (With Michael Elkin, Yuval Emek, and Dan Spielman)

Combinatorial Scientific Computing: Developed the first nearly linear-time algorithm for preconditioning and solving symmetric diagonally-dominant linear systems. Our work solved an open question posted by Pravin Vaidya in 1990. (With Dan Spielman).

Mesh Generation and Computational Geometry: Solved a major open question in three dimensional mesh generation by developing the first provably good technique to remove slivers and to generate well-shaped Delaunay meshes in three dimensions. (With Siu-Wing Chen, Tamal Dey, Herbert Edelsbrunner, and Mike Facello; and Xiang-Yang Li). Developed the sphere-packing based Delaunay and Voronoi meshing and coarsening algorithm in two and three dimensions (with Gary Miller, Dafna Talmor, and Noel Walkington).

Spectral Graph Theory and Graph Partitioning: Proved a significant result in spectral graph theory: From the second eigenvector of a planar graph, we can compute, in linear time, a partition whose the quality is as good as that can be achieved by the classic Lipton-Tarjan's planar separator algorithm. Our result also shows that the Fiedler value of a bounded-degree planar graph of n vertices in O(1/n). (With Dan Spielman).

Geometric Graph Partitioning and N-Body Simulation: Extended the separator theorem of Lipton-Tarjan to high dimensions by proving an optimal separator theorem for well-shaped meshes and nearest neighborhood graphs in any fixed dimensions (with Gary Miller, William Thurston, and Steve Vavasis). Developed the first optimal load balancing scheme for non-uniform N-body simulation in three dimensions.

Computational Geometry: Meshing and Robust Statistics: Developed the first randomized O(log n) time, n-processor algorithm for computing the k-nearest neighborhood graphs in any fixed dimensions (with Alan Frieze and Gary Miller), first optimal parallel algorithm for generating quadtrees and nearest neighborhood graphs (with Marshall Bern and David Eppstein), and first provably good parallel Delaunay meshing algorithm (with Dan Spielman and Alper Ungor). Proved the Rousseeuw-Hubert conjecture on regression depth, providing an important theorem for Robust Statistics and Inference (Nina Amenta, Marshall Bern, and David Eppstein).

Broad Research Interests: Published diversely in conferences including SIGGRAPH, Crypto, PPoPP, PODC, POPL, Mathematical Programming, Mesh Roundtable, STOC, FOCS, SODA, SPAA, SoCG and in journals including JACM, SIAM J. on Algorithms, Applied Numerical Mathematics, Mathematical Programming, Discrete Computational Geometry, SIAM J. Scientific Computing, J. of Engineering with Computers, TCS, IEEE Trans. on Computers, SIAM J. Matrix Analysis, ACM Transactions on Programming Languages and Systems, J. Parallel and Distributed Computing, J. of Cryptology, J. Computational Complexity.

Active Industry Collaboration and Real-World Products: Intel transistor-level logic simulation software, SHARK (with Khaira); Xerox PARC Matlab Mesh Partitioning Toolbox, MESHPART (with Gilbert); IBM Grandcentral Station and JCentral (with Lu, Ford, Pass, Eichstaedt and Kraft); and various Akamai products on Internet data analysis, performace monitoring, and internet mapping.

Inventions: Awarded seven US patents.


NSF Career Award: Geometric Methods for Numerical Computing, (1995-1998);

Alfred P. Sloan Research Fellowship: (1996-1998);

Hitachi Software Research: Human-user Identification Method, (1996-1998);

DOE ASCI Initiative: Center for Simulation of Advanced Rockets, (1997-2002)

NSF OPAAL Grant: Center for Process Simulation and Design, (1998-2001);

IBM Research Grant: Automatic Audio Summarization for Distance Learning, (1998-2000).

NSF Grant: A Cryptography Center for Research and Education, (2000-2003)

NSF Numerical Analysis Grant: The Eigenvalue Problem in Geometry and Combinatorial Optimization, (1999-2002);

NSF Theory Grant: The Spectral Analysis for Graph Partitioning, (2003-2006);

NSF Information Technologies Research Award: The Smoothed Analysis of Algorithms, (2003-2008).


COURSES:   During the last 14 years, I have taught several undergraduate courses in Computer Science and Applied Mathematics including the introductions to algorithms, programming languages, scientific computing, applied linear algebra, calculus, differential equations, computational geometry, cryptography and network security. At the graduate and upper undergraduate level, I have introduced several advanced courses including internet algorithms, parallel scientific computing, algorithms for new ages, and have taught advanced courses in algorithms, probability methods, and geometric methods. Click here for the list of the classes I taught in the past.

INVITED TALKS   Foundations of Computational Mathematics 2005 (Plenary); COCOON 2005 (Invited Speaker), First SIAM Workshop on Combinatorial Scientific Computing 2004 (Plenary), International Meshing Roundtable 2003 (Plenary), International Symposium on Computer and Information Sciences 2003 (Plenary), Jornadas Chilenas de Computacion (Keynote Conferencias).

ADVISING:   Kyle Burke [Combinatorial Scientific Computing], Kebin Wang [Cache Oblivious Algorithms], John Racklin [Bioinformatics] (his main advisor is Professor Simon Kasif), Konstantin Voevodski [Bioinformatics] (with Professor Simon Kasif), Yingchao Zhao (Tsinghua University). Click here for the list of students I previously advised, co-advised, and helped.

BOOK EDITOR:   Algorithms and Computation: Lecture Notes in Computer Science, Vol. 1969, Springer, 2000, D.T. Lee and S.-H. Teng (Eds.); Solving Irregularly Structured Problems in Parallel (ISBN 3-540-64809-7), Lecture Notes in Computer Science, Vol. 1457, Springer, 1998 5th International Symposium, IRREGULAR '98, Berkeley, California, USA, August 9-11, 1998, Afonso Ferreira, Jose D. P. Rolim, Horst Simon, and Shang-Hua Teng (Eds.)

PROGRAM COMMITTEE:   PC Chair ACM/SIAM SODA 2008, ACM/SIAM SODA 2006, LATIN'06, The First Workshop on Internet and Network Economies (WINE 2005), COCOON 2005, SIAM Conference on Computational Science and Engineering 2003, SoCG Video Committee, International Confernece on Parallel Processing 2003, ISAAC 2000 (co-chair), ACM SPAA 2000 (Chair), Panelist of Workshop on "Challenges for Theoretical Computer Science" 2000, STOC 1999, SPAA 1999, ACM SoCG Video Committee, ISAAC 1998, Organizer of mini-symposium on "The Multilevel Method" at SIAM Conference on Applied Linear Algebra 1997, International Mesh Roundtable 1997, EURO-PAR'97 (vice-chair), COCOON 1997, STOC 1996.


  Journal of Combinatorial Optimization; Journal of Computer and System Sciences.


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.