ABSTRACT

At the request of the International Mathematical Union, in 1999, Steve Smale proposed a list of 18 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 presents fundamental advances in this problem including the smoothed analysis of a randomized algorithm and a deterministic algorithm working in near-polynomial (i.e., NO(log log N) ) average time.