Theorists have been challenged by the existence of remarkable algorithms that are known by scientists and engineers to work well in practice, but whose theoretical analyses are negative or inconclusive. 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 overly optimistic because the random inputs it considers can bear little resemblance to those encountered in practice.

We propose an analysis that we call smoothed analysis that can help explain the success of many algorithms that both worst-case and average-case cannot. In smoothed analysis, we measure the performance of an algorithm under slight random perturbations of arbitrary inputs. In particular, we consider Gaussian perturbations of inputs to algorithms that take real and complex inputs, and we measure the running time of algorithms in terms of the input size and the variance of the perturbations. We show that the simplex algorithm has polynomial smoothed complexity.

The simplex algorithm is the classic example of an algorithm that performs well in practice but takes exponential time in the worst case. In the 1980's the simplex algorithm was shown to converge in expected polynomial time on various distributions of random inputs, most notably by Borgwardt and Smale. However, the last 20 years of research in probability and numerical analysis have taught us that these random instances have very special properties that one should not expect to find in practice.

For every matrix A with entries of absolute value at most 1, every vector c, and every vector b whose entries are 1 or -1, we show that the simplex algorithm using the shadow-vertex pivot rule takes expected time polynomial in 1/sigma and the sizes of A and c to solve:

minimize c'x s.t (A + \sigma G) x <= b

If A is well-scaled, then the solution to this program is an approximation to the original.

This is joint work with Daniel Spielman of MIT.