A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian

DOI10.1007/s10107-020-01558-2zbMath1478.90081arXiv1907.11686OpenAlexW3095481223MaRDI QIDQ2235162

Afonso S. Bandeira, Dmitriy Kunisky

Publication date: 20 October 2021

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1907.11686

zbMATH Keywords

convex optimizationsemidefinite programmingspin glasssum-of-squaresaverage-case computational complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30) Random matrices (algebraic aspects) (15B52) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Disordered systems insights on computational hardness, The Spectrum of the Grigoriev–Laurent Pseudomoments, Optimization of mean-field spin glasses

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparse sums of squares on finite abelian groups and improved semidefinite lifts
• Probability in Banach spaces. Isoperimetry and processes
• Spectral norm of products of random and deterministic matrices
• On the existence of equiangular tight frames
• Adaptive estimation of a quadratic functional by model selection.
• The Parisi ultrametricity conjecture
• The algorithmic hardness threshold for continuous random energy models
• Sum-of-squares hierarchy lower bounds for symmetric formulations
• Invertibility of random matrices: norm of the inverse
• Extremal cuts of sparse random graphs
• The Littlewood-Offord problem and invertibility of random matrices
• The Parisi formula
• Global Optimization with Polynomials and the Problem of Moments
• A Note on Extreme Correlation Matrices
• Sum-of-squares proofs and the quest toward optimal algorithms
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• SOS Is Not Obviously Automatizable, Even Approximately
• The Sherrington-Kirkpatrick Model
• Semidefinite Optimization and Convex Algebraic Geometry
• Following the Ground States of <scp>Full‐RSB</scp> Spherical Spin Glasses
• Reducibility among Combinatorial Problems
• On the Bit Complexity of Sum-of-Squares Proofs
• Lifting sum-of-squares lower bounds: degree-2 to degree-4
• Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective
• Semidefinite programs on sparse random graphs and their application to community detection
• Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
• Geometry of cuts and metrics