Felipe Cucker – On a Problem Posed by Steve Smale

May 22, 2014

cuckerAt 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.

Comments are closed.