Dan Spielman: Smoothed Analysis of Numerical Algorithms

Dan Spielman: Smoothed Analysis of Numerical Algorithms Smoothed analysis considers the behavior of algorithms assuming that their inputs are subject to slight random perturbations. We will survey some interesting results on the smoothed analysis of algorithms for solving systems of linear equations, systems of algebraic equations, and systems of linear inequalities. We hope to convey some of the techniques applied in these analyses, and to discuss how they might be improved.