On Smale's 17th problem over the reals
<|reference_start|>On Smale's 17th problem over the reals: We consider the problem of efficiently solving a system of $n$ non-linear equations in ${\mathbb R}^d$. 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(\sqrt{d\log d})$. If the maximal degree is very large, we also give an algorithm that works up to $n=d-1$.<|reference_end|>
@article{montanari2024on,
    title={On Smale's 17th problem over the reals},
    author={Andrea Montanari and Eliran Subag},
    journal={arXiv preprint arXiv:2405.01735},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.01735},
    primaryClass={cs.DS cs.NA math.NA math.OC math.PR}
}