Smoothed Analysis: Motivation and Discrete Models

Authors: Daniel A. Spielman, and Shang-Hua Teng .

Bibliographic Information: In the proceedings of WADS 2003, Lecture Notes in Computer Science, Springer-Verlag.


In smoothed analysis, one measures the complexity of algorithms assuming that their inputs are subject to small amounts of random noise. In an earlier work (Spielman and Teng, 2001) , we introduced this analysis to explain the good practical behavior of the simplex algorithm. In this paper, we provide further motivation for the smoothed analysis of algorithms, and develop models of noise suitable for analyzing the behavior of discrete algorithms. We then consider the smoothed complexities of testing some simple graph properties in these models.
You can download this paper as Postscript, compressed Postscript, PDF, or compressed PDF.
Daniel A. Spielman
Last modified: Fri Aug 3 00:21:05 EDT 2001