2008 Gödel Prize Goes to Yale's Spielman and Boston University's Teng

August 26, 2008

Daniel A. Spielman, professor of applied mathematics and computer science at Yale University, and Shang-Hua Teng, professor of computer science at Boston University, have been awarded the 2008 Gödel Prize.

Carrying a $5,000 honorarium, the prize recognizes breakthroughs in theoretical computer science. Spielman and Teng had used rigorous mathematical analysis to predict the performance of optimization tools on real data. Their paper, "Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time," appeared in the Journal of the Association for Computing Machinery in 2004.

The "smoothed analysis" technique helps predict the success of problem-solving with real data and computers. According to the ACM, the research represents a huge advance in addressing the challenge of predicting the performance of algorithms. Understanding the mathematical structure of these problems is necessary in the design of efficient protocols and software.

Spielman and Teng received the award from the Special Interest Group on Algorithms and Computing Theory of the ACM and the European Association for Theoretical Computer Science at the International Colloquium on Automata, Languages, and Programming last month in Reykjavik, Iceland.

Source: Yale University, Aug. 12, 2008; Association for Computing Machinery, May 28, 2008.