Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915231511347200 |
|---|---|
| author | Sellke, Mark |
| author_facet | Sellke, Mark |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_04632 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses Sellke, Mark Probability Disordered Systems and Neural Networks Data Structures and Algorithms Mathematical Physics 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. |
| title | Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses |
| topic | Probability Disordered Systems and Neural Networks Data Structures and Algorithms Mathematical Physics |
| url | https://arxiv.org/abs/2504.04632 |