# Shang-Hua Teng

> Chinese-American computer scientist (b.1964)

**Wikidata**: [Q92663](https://www.wikidata.org/wiki/Q92663)  
**Wikipedia**: [English](https://en.wikipedia.org/wiki/Shang-Hua_Teng)  
**Source**: https://4ort.xyz/entity/shang-hua-teng

## Summary
Shang-Hua Teng is a prominent Chinese-American computer scientist and mathematician recognized for his foundational contributions to theoretical computer science and algorithm design. He is a two-time recipient of the Gödel Prize and is best known for pioneering "smoothed analysis," a method that explains the practical efficiency of algorithms.

## Biography
- Born: 1964, Beijing, China
- Nationality: People's Republic of China
- Education: Shanghai Jiao Tong University; University of Southern California; Carnegie Mellon University; USC Viterbi School of Engineering
- Known for: Smoothed analysis of linear programming and nearly-linear time Laplacian solvers
- Employer(s): University of Southern California, Massachusetts Institute of Technology (MIT), IBM, University of Illinois Urbana–Champaign, University of Minnesota, Boston University
- Field(s): Computer Science, Mathematics, Engineering

## Contributions
Shang-Hua Teng has made foundational contributions to the field of algorithms and theoretical computer science. One of his most recognized works is the development of "smoothed analysis" of linear programming, a framework that helps explain why certain algorithms perform well in practice despite poor worst-case theoretical performance. This work earned him his first Gödel Prize in 2008. He received a second Gödel Prize in 2015 for his research regarding nearly-linear time Laplacian solvers. 

His research spans scalable algorithm design, mesh generation, and algorithmic game theory. He has also contributed to interdisciplinary applications of computing, bridging the gap between mathematical theory and practical computational application. Throughout his career, he has collaborated with notable figures like his doctoral advisor Gary Miller and mentored several doctoral students who have gone on to contribute to the field, including Yu Cheng, Xiang-Yang Li, Jiaowen Yang, Alper Üngör, Kyle Webster Burke, Kebin Wang, and Konstantin Voevodski. His work has been influential across the software and IT service management industries, supported by his affiliations with major research institutions and corporations like IBM.

## FAQs
### Q: What is Shang-Hua Teng's most significant scientific contribution?
A: He is most famous for pioneering "smoothed analysis," which provides a mathematical bridge between the average-case and worst-case performance of algorithms, specifically in linear programming.

### Q: How many times has Shang-Hua Teng won the Gödel Prize?
A: He has won the Gödel Prize twice, first in 2008 for smoothed analysis and again in 2015 for his work on nearly-linear time Laplacian solvers.

### Q: Which professional organizations have recognized Shang-Hua Teng?
A: He was named an ACM Fellow in 2009 and a Fellow of the Society for Industrial and Applied Mathematics (SIAM) in 2021 for his contributions to scalable algorithm design and algorithmic game theory.

## Why They Matter
Shang-Hua Teng’s work has fundamentally changed how computer scientists evaluate algorithm efficiency. By introducing smoothed analysis, he provided a mathematical justification for the success of algorithms that were previously considered inefficient under traditional worst-case analysis. This has had a lasting impact on linear programming, numerical analysis, and the broader software industry. 

Furthermore, his work on nearly-linear time solvers for Laplacian systems has influenced the development of faster algorithms for graph-related problems, which are essential in modern computing. His influence extends through an extensive academic career at top-tier universities like MIT, USC, and the University of Illinois Urbana–Champaign. As an ACM Fellow and a Fellow of the Society for Industrial and Applied Mathematics (SIAM), his leadership in theoretical computer science is widely recognized. His mentorship of numerous doctoral students ensures that his methodologies and focus on scalable algorithm design continue to influence the field of computer science and engineering. Without his contributions, the theoretical understanding of practical algorithm performance would lack the rigorous foundation provided by his research.

## Notable For
*   **Two-time Gödel Prize winner:** Received the prestigious award in 2008 and 2015 for landmark papers in theoretical computer science.
*   **Fulkerson Prize (2009):** Awarded for outstanding papers in the field of discrete mathematics.
*   **Smoothed Analysis Pioneer:** Created the framework for analyzing the complexity of algorithms under slight perturbations of the input.
*   **ACM and SIAM Fellow:** Recognized by the Association for Computing Machinery (2009) and the Society for Industrial and Applied Mathematics (2021) for career-long excellence.
*   **Erdős Number 2:** Reflects a high degree of collaborative proximity to the mathematician Paul Erdős.

## Body
### Academic Career and Affiliations
Shang-Hua Teng has held numerous prestigious positions across academia and industry. He has served as a faculty member or researcher at the Massachusetts Institute of Technology (MIT), the University of Southern California (USC), the University of Illinois Urbana–Champaign, the University of Minnesota, and Boston University. In the corporate sector, he was affiliated with the American multinational technology corporation IBM.

### Research and Theoretical Contributions
Teng's research focuses on the intersection of mathematics and computer science. His work in scalable algorithm design and mesh generation has been central to his career. He is particularly noted for his contributions to algorithmic game theory and the smoothed analysis of linear programming. His 2021 SIAM Fellowship citation specifically highlights his work in these areas, as well as his pioneering role in smoothed analysis.

### Mentorship and Collaboration
Teng completed his doctoral studies at the University of Southern California under the advisement of Gary Miller. He has since advised a significant number of doctoral students, including:
*   Xiang-Yang Li
*   Jiaowen Yang
*   Alper Üngör
*   Kyle Webster Burke
*   Kebin Wang
*   Konstantin Voevodski
*   Yu Cheng

### Professional Recognition
In addition to his major prizes, Teng was elected as an ACM Fellow in 2009 for "contributions to theoretical computer science, algorithms and interdisciplinary applications of computing." His 2021 SIAM Fellowship recognized him for "contributions to scalable algorithm design, mesh generation, and algorithmic game theory, and for pioneering smoothed analysis of linear programming."

```json
{
  "@context": "https://schema.org",
  "@type": "Person",
  "name": "Shang-Hua Teng",
  "jobTitle": "Computer Scientist",
  "worksFor": [
    {"@type": "Organization", "name": "University of Southern California"},
    {"@type": "Organization", "name": "Massachusetts Institute of Technology"},
    {"@type": "Organization", "name": "IBM"},
    {"@type": "Organization", "name": "University of Illinois Urbana–Champaign"},
    {"@type": "Organization", "name": "University of Minnesota"},
    {"@type": "Organization", "name": "Boston University"}
  ],
  "nationality": {"@type": "Country", "name": "People's Republic of China"},
  "birthDate": "1964",
  "birthPlace": "Beijing, China",
  "alumniOf": [
    {"@type": "EducationalOrganization", "name": "Shanghai Jiao Tong University"},
    {"@type": "EducationalOrganization", "name": "University of Southern California"},
    {"@type": "EducationalOrganization", "name": "Carnegie Mellon University"}
  ],
  "knowsAbout": ["Theoretical Computer Science", "Algorithms", "Linear Programming", "Smoothed Analysis", "Algorithmic Game Theory"],
  "sameAs": ["https://www.wikidata.org/wiki/Q93011", "https://en.wikipedia.org/wiki/Shang-Hua_Teng"],
  "description": "Chinese-American computer scientist known for his work on smoothed analysis and two-time winner of the Gödel Prize."
}

## References

1. [Source](https://sigact.org/prizes/g%C3%B6del.html)
2. [Source](https://www.acm.org/media-center/2009/december/acm-names-47-fellows-for-innovations-in-computing-information-technology)
3. [Source](https://www.ams.org/prizes-awards/pabrowse.cgi?parent_id=17)
4. [Source](https://www.siam.org/prizes-recognition/fellows-program/all-siam-fellows?page=3)
5. Mathematics Genealogy Project
6. Virtual International Authority File
7. Freebase Data Dumps. 2013
8. [‪Shanghua Teng‬ - ‪Google Scholar‬](https://scholar.google.com/citations?user=tn29sAQAAAAJ)