Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses
Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses
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.
Mark Sellke
物理学
Mark Sellke.Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses[EB/OL].(2025-04-06)[2025-06-30].https://arxiv.org/abs/2504.04632.点此复制
评论