ShangHua Teng
Professor of
Computer Science at
Boston University

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 UrbanaChampaign, 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
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, Online Scheduling, VLSI and Circuit Simulation, Largescale 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. 
Computational Game Theory: Solved a major open question in Computational Game Theory by showing that the problems of finding a Nash equilibrium of a twoplayer game and of finding a market equilibrium of a Leontief economy DO NOT have a fully polynomialtime approximation scheme, unless PPAD is in P. Furthermore, proved that the smoothed complexity of the classic LemkeHowson 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; LiSha Huang; and Paul Valiant).
NearlyLinear Time Graph Algorithms: Developed the first nearly lineartime 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(log^{2} n loglog n) and developed a nearly lineartime algorithm for construting the lowstretch spanning tree. (With Michael Elkin, Yuval Emek, and Dan Spielman)
Combinatorial Scientific Computing: Developed the first nearly lineartime algorithm for preconditioning and solving symmetric diagonallydominant 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 wellshaped Delaunay meshes in three dimensions. (With SiuWing Chen, Tamal Dey, Herbert Edelsbrunner, and Mike Facello; and XiangYang Li). Developed the spherepacking 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 LiptonTarjan's planar separator algorithm. Our result also shows that the Fiedler value of a boundeddegree planar graph of n vertices in O(1/n). (With Dan Spielman).
Geometric Graph Partitioning and NBody Simulation: Extended the separator theorem of LiptonTarjan to high dimensions by proving an optimal separator theorem for wellshaped 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 nonuniform Nbody simulation in three dimensions.
Computational Geometry: Meshing and Robust Statistics: Developed the first randomized O(log n) time, nprocessor algorithm for computing the knearest 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 RousseeuwHubert 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 RealWorld Products: Intel transistorlevel 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.
Alfred P. Sloan Research Fellowship: (19961998);
Hitachi Software Research: Humanuser Identification Method, (19961998);
DOE ASCI Initiative: Center for Simulation of Advanced Rockets, (19972002)
NSF OPAAL Grant: Center for Process Simulation and Design, (19982001);
IBM Research Grant: Automatic Audio Summarization for Distance Learning, (19982000).
NSF Grant: A Cryptography Center for Research and Education, (20002003)
NSF Numerical Analysis Grant: The Eigenvalue Problem in Geometry and Combinatorial Optimization, (19992002);
NSF Theory Grant: The Spectral Analysis for Graph Partitioning, (20032006);
NSF Information Technologies Research Award: The Smoothed Analysis of Algorithms, (20032008).
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, coadvised, 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 3540648097), Lecture Notes in Computer Science, Vol. 1457, Springer, 1998 5th International Symposium, IRREGULAR '98, Berkeley, California, USA, August 911, 1998, Afonso Ferreira, Jose D. P. Rolim, Horst Simon, and ShangHua 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 (cochair), 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 minisymposium on "The Multilevel Method" at SIAM Conference on Applied Linear Algebra 1997, International Mesh Roundtable 1997, EUROPAR'97 (vicechair), COCOON 1997, STOC 1996.  
JOURNAL EDITOR:  Journal of Combinatorial Optimization; Journal of Computer and System Sciences. 