### 2008 Gödel Prize

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.

#### Award Committee

- Volker Diekert (Universität Stuttgart), chair
- Shafi Goldwasser (MIT and Weizmann Institute)
- Johan Håstad (KTH Stockholm)
- Jean-Pierre Jouannaud (INRIA and Tsinghua University)
- Christos Papadimitriou (UC Berkeley)
- Colin Stirling (University of Edinburgh)