Felipe Cucker: On a Problem posed by Steve Smale
Felipe Cucker, City University of Hong Kong
Time: Mon 2012-08-27 15.15 - 16.15
Location: Room 3721, Lindstedsvägen 25, Department of Mathematics, KTH
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).