On a Problem posed by Steve Smale

Joint CS Theory Group & Department of Mathematics Seminar

Title: On a Problem posed by Steve Smale

Speaker: Felipe Cucker, City University of Hong Kong
http://www6.cityu.edu.hk/ma/people/cucker.html

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 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 accepted in Annals of Mathematics
A preliminary version of the paper appeared in STOC'10

More details available at
http://cse.hkust.edu.hk/tcsc/seminars.html
http://intranet.math.ust.hk/seminars/abstract.asp?635