Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses

Abstract

We prove constant degree polynomial algorithms cannot optimize pure spherical $p$-spin Hamiltonians beyond the algorithmic threshold $\mathsf{ALG}(p)=2\sqrt{\frac{p-1}{p}}$. 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.

arXiv comment18 pages