July 15, 9:30 ~ 10:30
Finding one root of a polynomial system: Smale's 17th problem
Inria, France - email@example.com
How many operations are sufficient to numerically compute one root of a polynomial system of equations? Smale's 17th problem asks whether a polynomial complexity is possible for random systems. We now have a thorough answer. Based on work by Beltrán, Bürgisser, Cucker, Pardo, Shub, Smale and myself, I will explain the main ideas that underlie it, from effective Newton's method estimates to the sampling of random system-solution pairs.