On Smale's 17th problem over the reals
Seminar
Speaker
Eliran Subag (Weizmann Institute)
Date
17/05/2026 - 13:00 - 12:00Add to Calendar
2026-05-17 12:00:00
2026-05-17 13:00:00
On Smale's 17th problem over the reals
In 1998, Smale published his `list of mathematical problems for the next century'. His 17th problem asked if a zero of d random polynomials in d unknowns can be found by an algorithm in polynomial time on average. In its original formulation, concerning the complex setting, Smale's problem was recently resolved. In the real, much more difficult case, almost nothing is known.In the first part of the talk I will present new algorithms for Smale's problem over the reals for systems of d-O(\sqrt{d\log(d)}) polynomials in d variables. In the second part, I will briefly discuss a related problem in which we expect an algorithmic phase transition: once a certain parameter crosses a threshold value, although there are exponentially many solutions in d, finding a solution is algorithmically hard. Time permitting, I will explain how those questions are related to fundamental problems in the theoretical physics of spin glasses from the 1980s, which were solved only recently. Based on joint works with Andrea Montanari.
Building 503, room 226 and Zoom: https://biu-ac-il.zoom.us/j/85162486342
אוניברסיטת בר-אילן - המחלקה למתמטיקה
mathoffice@math.biu.ac.il
Asia/Jerusalem
public
Place
Building 503, room 226 and Zoom: https://biu-ac-il.zoom.us/j/85162486342
Abstract
In 1998, Smale published his `list of mathematical problems for the next century'. His 17th problem asked if a zero of d random polynomials in d unknowns can be found by an algorithm in polynomial time on average. In its original formulation, concerning the complex setting, Smale's problem was recently resolved. In the real, much more difficult case, almost nothing is known.
In the first part of the talk I will present new algorithms for Smale's problem over the reals for systems of d-O(\sqrt{d\log(d)}) polynomials in d variables. In the second part, I will briefly discuss a related problem in which we expect an algorithmic phase transition: once a certain parameter crosses a threshold value, although there are exponentially many solutions in d, finding a solution is algorithmically hard. Time permitting, I will explain how those questions are related to fundamental problems in the theoretical physics of spin glasses from the 1980s, which were solved only recently.
Based on joint works with Andrea Montanari.
תאריך עדכון אחרון : 13/05/2026
