In 1998, Smale published his `list of mathematical problems for the next century'. His 17th problem asked if a zero of d random complex polynomials in d unknowns can be found by an algorithm in polynomial time on average. Beltrán and Pardo proved the existence of an efficient randomized algorithm and Lairez recently showed it can be de-randomized to produce a deterministic efficient algorithm. This solved Smale's problem in its original complex form. In the real, more difficult case, almost nothing is known. First, 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. Then I will briefly discuss a related problem in which we expect a phase transition: once a certain parameter crosses a threshold value, although there are exponentially many solutions in d, finding a solution by an efficient algorithm should be impossible. Time permitting, I will explain how the above is related to fundamental problems from the 80s in the study of spin glasses in theoretical physics, which were solved very recently. Based on joint work with Andrea Montanari.