Fall 2014

A Deterministic Solution to Smale's 17th Problem

Wednesday, Dec. 16, 2015 9:00 am9:45 am PST

Add to Calendar


Calvin Lab

I will describe a deterministic algorithm that computes an approximate root of n complex polynomial equations in n unknowns in average polynomial time with respect to the size of the input, in the Blum-Shub-Smale model with square root. It rests upon a derandomization of an algorithm of Beltrán and Pardo and gives a deterministic affirmative answer to Smale’s 17th problem. The main idea is to make use of the randomness contained in the input itself.