ACM TechNews

Yale's Spielman Wins Godel Prize for Showing How Computer Algorithms Solve Problems

Yale University Office of Public Affairs (08/12/08)

The Association for Computing Machinery's (ACM's) Special Interest Group on Algorithms and Computing Theory (SIGACT) and the European Association for Theoretical Computer Science (EATCS) presented Daniel A. Spielman and Shang-Hua Teng with the Godel Prize during the International Colloquium on Automata, Languages, and Programming in Reykjavik, Iceland. Spielman, a professor of applied mathematics and computer science at Yale University, and Teng, a professor of computer science at Boston University, received the prestigious award for their research involving the Smoothed Analysis technique. The paper, "Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time," was published in the Journal of the Association for Computing Machinery in 2004. The mathematical analysis represents a major development in predicting the performance of optimization tools for real data, says ACM, because the mathematical structure needs to be understood to design efficient protocols and software. Spielman and Teng will share the prize's $5,000 award for their contribution to theoretical computer science.

http://opa.yale.edu/news/article.aspx?id=5937

---

© Copyright 2008 Information, Inc. This service may be reproduced for internal distribution.