On Smale's 17th problem over the reals

May 02, 2024 Β· Declared Dead Β· πŸ› arXiv.org

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Andrea Montanari, Eliran Subag arXiv ID 2405.01735 Category cs.DS: Data Structures & Algorithms Cross-listed math.NA, math.OC, math.PR Citations 4 Venue arXiv.org Last Checked 4 months ago
Abstract
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Γ‘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 a polynomial time algorithm that finds solutions (with high probability) for $n= d -O(\sqrt{d\log d})$ if the maximal degree is bounded by $d^2$ and for $n=d-1$ if the maximal degree is larger than $d^2$.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted