Title: Smoothed Analysis of the Simplex Method by Spielman & Teng

Spielman and Teng introduced a new type of analysis for the complexity of algorithms. This so-called "smoothed" analysis is a hybrid between worst case and average case analysis of algortihms. The performance of algorithms is studied under small random perturbations of their inputs. This talks presents the results of the smoothed analysis of the Simplex Method by Spielman and Teng and it explains the basic ideas of the proof.