Yale University
The Smoothed Analysis of Algorithms
3:30 - 5:30pm Monday, December 08, 2008
Regency D
Theorists have long been challenged by the existence of remarkable algorithms that are known by scientists and engineers to work well in practice, but whose theoretical analyses have been negative or unconvincing. The root of the problem is that algorithms are usually analyzed in one of two ways: by worst-case or average-case analysis. The former can improperly suggest that an algorithm will perform poorly, while the latter can be unconvincing because the random inputs it considers may fail to resemble those encountered in practice. Smoothed analysis can help explain the success of many algorithms that both worst-case and average-case analyses cannot. In smoothed analysis, we measure the performance of an algorithm under slight random perturbations of arbitrary inputs, and bound the performance as a function of the size of the input and the magnitude of the perturbation. If an algorithm has low smoothed complexity, then it should perform well if its inputs are subject to random noise. We will explain how smoothed analysis has been used to analyze the behavior of many algorithms and heuristics, including the simplex algorithm, the Perceptron algorithm Gaussian Elimination with partial pivoting, and k-means clustering.
http://www.cs.yale.edu/homes/spielman/nips08/index.html
Daniel Spielman is a Professor of Applied Mathematics and Computer Science at Yale University. He received his B.A. in Mathematics and Computer Science from Yale in 1992, and his Ph.D in Applied Mathematics from M.I.T. in 1995. He spent a year as a post-doc in Computer Science at U.C. Berkeley, and then taught in the Applied Mathematics department at M.I.T. until 2005. The awards he has received include the 1995 ACM Doctoral Dissertation Award, the 2002 IEEE Information Theory Paper Award, and most recently the 2008 Gödel Prize for his work on Smoothed Analysis. His main research interests include the design and analysis of algorithms, graph theory, and combinatorial scientific computing.
Flash Movie Session A