May 22, 2014
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 talk describes fundamental advances in this problem including the smoothed analysis of a randomized algorithm and a deterministic algorithm working in near-polynomial average time.
