Media Relations

News Releases

For Release Upon Receipt - June 5, 2008
Contact: Ronald Rosenberg, 617-358-1240, ronrosen@bu.edu

BOSTON UNIVERSITY PROFESSOR SHANG-HUA TENG'S RESEARCH WINS PRESTIGOUS AWARD FOR HELPING COMPUTERS SOLVE PRACTICAL PROBLEMS

(Boston) - Shang-Hua Teng, a Boston University Professor of Computer Science will share the prestigious Gödel Prize, given for outstanding papers in theoretical science, by the Association for Computing Machinery’s Special Interest Group on Algorithms and Computing Theory and the European Association for Theoretical Computer Science.

Together with long-time collaborator and friend Daniel A. Spielman, a Yale University professor of applied mathematics and computer science, they will travel to Reykjavik, Iceland next month to receive their award at the International Colloquium on Automata, Languages and Programming. They will be honored for their research in developing a rigorous framework to explain the practical success of algorithms on real data and real computers that could not be easily understood through traditional techniques.

Their paper, “Smoothed Analysis of Algorithms: Why is the Simplex Algorithm Usually Takes Polynomial Time,” explains why the Simplex Method, which is used to solve complex efficiency problems such as scheduling different airline fare classes, production planning, and games of strategy, functions so well, especially in business.

Smoothed analysis is considered an important development because it overcomes the “worst-case analysis,” which is a traditional way computer scientists analyze the amounts of resources required for the execution of algorithms, such as execution time, for the most difficult problem configuration.

However, the worst case analysis may not provide a complete picture of an algorithm’s resource requirements. For the Simplex Method, the worst case behavior was rarely encountered in practice. While computer scientists could contrive certain aberrant problem configurations that would cause the Simplex Method to falter, stretching out the running time to find a solution, this was an unusual situation in practice that could not be rigorously explained.

Teng and Spielman’s smoothed analysis of algorithms provides a framework to explain the success in practice of certain algorithms and heuristics (a problem-solving technique in which the best solution is selected at successive stages of a computer program). Instead of the traditional worst-case analysis, they proposed to analyze how small random changes to problem configurations given to an algorithm can alter its resource requirements. They proved why the Simplex Algorithm – first developed more than 50 years ago -- efficiently gave the correct problem-solving answers in practice. The researchers also showed that by introducing even small random changes to the aberrant problem configurations, the Simplex Method could efficiently find the solution.

In developing a new way to analyze the algorithms with smoothed analysis, they provided mathematicians and computer scientists with an extra level of confidence in understanding algorithm behavior. Teng and Spielman essentially provided a deeper and thorough understanding of why the widely known Simplex Method worked so well.

In 1992, when Teng, was an instructor at the Massachusetts Institute of Technology and Spielman, a Ph.D. candidate their student-teacher relationship evolved to where they began collaborating on improving the simplex method in 1996.

Over the years their research changed direction and in 2004 they published their seminal explanation paper in the Journal of the Association for Computing Machinery – the basis for winning the Gödel prize. The award, which includes $5,000, recognizes groundbreaking work in mathematical logic and computer science. Along the way, their research was cited as one of the three significant accomplishments funded by the computer science division of the National Science Foundation.

Since joining the faculty at Boston University in January, 2002, Teng has taught undergraduate and graduate classes in geometric algorithms, cryptography and computational geometry. In the fall of 2008 he will teach a new course in computational game theory.

“This [computer game theory] is a hot area at the juncture of economics and computer science where Shang-Hua and his collaborators are answering important open questions….stay tuned,” said Stan Sclaroff, Professor and Chairman of the Department of Computer Science.

Founded in 1839, Boston University is an internationally recognized institution of higher education and research. With more than 30,000 students, it is the fourth largest independent university in the United States. BU consists of 17 colleges and schools along with a number of multi-disciplinary centers and institutes which are central to the school's research and teaching mission.


— 30 —