On Smale's 17th problem over the reals

We consider the problem of efficiently solving a system of n non-linear equations in Rᵈ. Addressing Smale's 17th problem stated in 1998, we consider a setting whereby the n equations are random homogeneous polynomials of arbitrary degrees. In the complex case and for $n= d-1$, Beltr\'{a}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. Here we consider the real setting, to which previously developed methods do not apply. We describe an algorithm that efficiently finds solutions (with high probability) for n= d -O(√dlog d). If the maximal degree is very large, we also give an algorithm that works up to $n=d-1$.