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 . 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 也一样。你提问,回答直接引用原文。
它引用的顶会 Paper5
- The Algorithmic Phase Transition of Random k-SAT for Low Degree PolynomialsGuy Bresler, Brice HuangFOCS 2021 · 被引用 32 次
- Algorithms and Barriers in the Symmetric Binary Perceptron ModelDavid Gamarnik, Eren C. Kizildag, Will Perkins, Changji XuFOCS 2022 · 被引用 26 次
- Tight Lipschitz Hardness for optimizing Mean Field Spin GlassesBrice Huang, Mark SellkeFOCS 2022 · 被引用 21 次
- Potential Hessian Ascent: The Sherrington-Kirkpatrick ModelDavid Jekel, Juspreet Singh Sandhu, Jonathan ShiSODA 2025 · 被引用 3 次
- Discrepancy Algorithms for the Binary PerceptronShuangping Li, Tselil Schramm, Kangjie ZhouSTOC 2025 · 被引用 1 次
相关 Paper
- 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 次
- Graph Colouring Is Hard on Average for Polynomial Calculus and NullstellensatzJonas Conneryd, Susanna F. de Rezende, Jakob Nordström, Shuo Pang 等FOCS 2023
- Low-Degree Hardness of Random Optimization ProblemsDavid Gamarnik, Aukosh Jagannath, Alexander S. WeinFOCS 2020 · 被引用 48 次
- The complexity of approximating averages on bounded-degree graphsAndreas Galanis, Daniel Stefankovic, Eric VigodaFOCS 2020 · 被引用 1 次
