Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses
Mark Sellke
2025Year
5Citations
Abstract
We prove constant degree polynomial algorithms cannot optimize pure spherical p-spin Hamiltonians beyond the algorithmic threshold . 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.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext 585fb2bb-b341-4bd4-bf20-0b047fd0d2eeBuilds on5
- The Algorithmic Phase Transition of Random k-SAT for Low Degree PolynomialsGuy Bresler, Brice HuangFOCS 2021 · 32 citations
- Algorithms and Barriers in the Symmetric Binary Perceptron ModelDavid Gamarnik, Eren C. Kizildag, Will Perkins, Changji XuFOCS 2022 · 26 citations
- Tight Lipschitz Hardness for optimizing Mean Field Spin GlassesBrice Huang, Mark SellkeFOCS 2022 · 21 citations
- Potential Hessian Ascent: The Sherrington-Kirkpatrick ModelDavid Jekel, Juspreet Singh Sandhu, Jonathan ShiSODA 2025 · 3 citations
- Discrepancy Algorithms for the Binary PerceptronShuangping Li, Tselil Schramm, Kangjie ZhouSTOC 2025 · 1 citation
Related papers
- Solving the Hamilton cycle problem fast on averageMichael AnastosFOCS 2022
- Sharp Phase Transitions in Estimation with Low-Degree PolynomialsYoungtak Sohn, Alexander S. WeinSTOC 2025 · 1 citation
- Graph Colouring Is Hard on Average for Polynomial Calculus and NullstellensatzJonas Conneryd, Susanna F. de Rezende, Jakob Nordström, Shuo Pang et al.FOCS 2023
- Low-Degree Hardness of Random Optimization ProblemsDavid Gamarnik, Aukosh Jagannath, Alexander S. WeinFOCS 2020 · 48 citations
- The complexity of approximating averages on bounded-degree graphsAndreas Galanis, Daniel Stefankovic, Eric VigodaFOCS 2020 · 1 citation
