|国家预印本平台
首页|Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses

Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses

Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses

来源:Arxiv_logoArxiv
英文摘要

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.点此复制

评论