Felipe Cucker: On a Problem posed by Steve Smale

At the request of the International Mathematical Union, in 1999, Steve Smale proposed a list of 19 problems for the mathematicians of the 21st century. The 17th of these problems asks for the existence of a deterministic algorithm computing an approximate solution of a system of $n$ complex polynomials in $n$ unknowns in time polynomial, on the average, in the size $N$ of the input system. The paper gives fundamental advances in this problem including the smoothed analysis of a randomized algorithm and a deterministic algorithm working in near-polynomial (i.e., N^{O(\log\log N)}) average time.

Paper published in Annals of Mathematics (extended abstract appeared at STOC 2010).