Joint Seminar with Department of Mathematics

Title: On a Problem posed by Steve Smale

Speaker: Felipe Cucker, City University of Hong Kong

Time/Date:  Friday, Mar 11, 2-3PM
Room 3401

Abstract:
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 algorith
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 accepted in Annals of Mathematics
The preliminary version of the paper was in STOC'10