Abstract
The 17th of the problems proposed by Steve Smale for the 21st century is concerned with the complexity for computing an approximate solution of a given system of $n$ complex polynomials in $n$ unknowns. More specifically, the 17th problem asks for a deterministic algorithm for this task that runs in time polynomial, on the average, in the size $N$ of the input system.
In joint work with Felipe Cucker, we managed to perform a smoothed analysis (in the sense of Spielman and Teng) of a linear homotopy algorithm for this problem that uses a random starting system. The smoothed complexity is polynomial in the input size and the variance of the random perturbation of the input systems. The techniques developed for this allow to exhibit and analyze a deterministic algorithm for computing an approximate solution that has an average complexity $N^{\Oh(\log\log N)}$, which is nearly a solution to Smale's 17th problem.
The methodology appears to be quite general: for instance it leads to new algorithms for computing eigenvalues and eigenvectors of matrices that can be shown to run in smoothed polynomial time.