Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses

Sellke, Mark

数学 > 概率

arXiv:2504.04632 (math)

[提交于 2025年4月6日 ]

标题：纯球面自旋玻璃优化的低度硬度假设

标题： Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses

Authors:Mark Sellke

摘要：我们证明了常数次数的多项式算法无法优化纯球面上的$p$-自旋哈密顿量，超越算法阈值$\mathsf{ALG}(p)=2\sqrt{\frac{p-1}{p}}$。该证明通过将任何假设的此类算法转化为一个李普希茨函数来实现，对于李普希茨函数的硬度，作者与B. Huang之前已经证明过。

摘要： 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.

评论：	18页
主题：	概率 (math.PR) ; 无序系统与神经网络 (cond-mat.dis-nn); 数据结构与算法 (cs.DS); 数学物理 (math-ph)
引用方式：	arXiv:2504.04632 [math.PR]
	(或者 arXiv:2504.04632v1 [math.PR] 对于此版本)
	https://doi.org/10.48550/arXiv.2504.04632

提交历史

来自： Mark Sellke [查看电子邮件]
[v1] 星期日， 2025 年 4 月 6 日 22:01:47 UTC (49 KB)

数学 > 概率

标题：纯球面自旋玻璃优化的低度硬度假设

标题： Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses

提交历史

获取论文：

参考文献与引用

收藏

文献和引用工具

与本文相关的代码，数据和媒体

演示

推荐器和搜索工具

arXivLabs：与社区合作伙伴的实验项目

数学 > 概率

标题： 纯球面自旋玻璃优化的低度硬度假设 显示英文标题

标题： Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses

提交历史

获取论文：

参考文献与引用

BibTeX 格式的引用

收藏

文献和引用工具

与本文相关的代码，数据和媒体

演示

推荐器和搜索工具

arXivLabs：与社区合作伙伴的实验项目

标题：纯球面自旋玻璃优化的低度硬度假设