The Complexity of Bezout’s Theorem: From Algebraic Geometry to Optimal Transport

In their seminal work “Complexity of Bezout’s Theorem,” Mike Shub and Steve Smale developed a geometric framework to study the complexity of solving polynomial systems. This program introduced ideas that connect algebraic geometry, probability, and complexity theory, with key concepts including homotopy methods, condition numbers, and intersection theory. A major milestone in this field was the solution of Smale’s 17th problem—finding a zero of a polynomial, on average, in polynomial time—through the contributions of Beltrán and Pardo, Bürgisser and Cucker, and Lairez.

In this talk, I will outline the geometric aspects of this program, tracing its origins and broader developments. I will revisit Shub and Smale’s original proposal to study geodesics in the "condition metric" and demonstrate how optimal transport provides a new perspective, reconnecting with the foundational ideas of the story.