Lune

FOCS2025顶会

Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses

Mark Sellke

2025年份
5被引次数

摘要

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

问问这篇 Paper

智能体会读完全文。

Lune 把这篇 Paper 索引到了最后一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。

可以从这些问题问起

智能体调用

Luneget_paper_fulltext

在 Lune 里问

免费开始,无需绑卡

lune papers fulltext 585fb2bb-b341-4bd4-bf20-0b047fd0d2ee

它引用的顶会 Paper5

相关 Paper

黄昏的海面,两侧是细线勾勒的悬崖