The 2008 Gödel Prize for outstanding papers in the area of theoretical computer science is awarded to Daniel A. Spielman and Shang-Hua Teng for their paper:
Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time by Daniel A. Spielman and Shang-Hua Teng, Journal of the ACM (JACM), 51(3), May 2004, 385-463.
First presented at the Annual ACM Symposium on the Theory of Computing (STOC 01), 2001, 296-305.
Smoothed Analysis is a novel approach to the analysis of algorithms. It bridges the gap between worst-case and average case behavior by considering the performance of algorithms under a small perturbation of the input. As a result, it provides a new rigorous framework for explaining the practical success of algorithms and heuristics that could not be well understood through traditional algorithm analysis methods. The paper establishes that the classical simplex method due to George Danzig (1947) for the problem of linear programming, even though of exponential worst-case complexity, has polynomial smoothed complexity. Linear programming is a broad and fundamental class of problems and Simplex is widely used in practice.
The framework of smoothed analysis introduced by Spielman and Teng relies on deep mathematical analysis and insight Since its appearance in 2001 there has been a large amount of research based on it, evidence of its importance to Theoretical Computer Science, as well as to other disciplines.
The paper is an important step forward in meeting the grand challenge of developing means for predicting the performance of algorithms and heuristics on real data and on real computers.