Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses
Not on the map. Why?
Abstract (arXiv)
We prove constant degree polynomial algorithms cannot optimize pure spherical p-spin Hamiltonians beyond the algorithmic threshold mathsfALG(p)=2√fracp-1p. The proof goes by transforming any hypothetical such algorithm into a Lipschitz one, for which hardness was shown previously by the author and B. Huang.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). First posted on arXiv 6 Apr 2025.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2026: 1.
1 paper.