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

DOI10.1007/S10107-020-01558-2MaRDI QIDQ2235162zbMATH OpenOpenAlexFDO

Authors Dmitriy Kunisky, Afonso S. Bandeira

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

average-case computational complexityconvex optimizationsemidefinite programmingspin glasssum-of-squares

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) 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) Semidefinite programming (90C22)

Abstract: We show that, if $mathbfWinmathbb{R}_{mathsfsym}^{NimesN}$ is drawn from the gaussian orthogonal ensemble, then with high probability the degree 4 sum-of-squares relaxation cannot certify an upper bound on the objective $N^{-1}cdotmathbf{x}^{o}pmathbfWmathbfx$ under the constraints $x_i^2-1=0$ (i.e. $mathbfxin{pm1}^N$) that is asymptotically smaller than $lambd{a}_{max}(mathbfW)approx2$. We also conjecture a proof technique for lower bounds against sum-of-squares relaxations of any degree held constant as $Noinfty$, by proposing an approximate pseudomoment construction.

Recommendations

• Optimized lower bounds forN-body Hamiltonians
• Optimization of the Sherrington--Kirkpatrick Hamiltonian
• Bounds for tentacular Hamiltonians
• A lower bound for the spectrum of \(N\)-particle Hamiltonians
• Asymptotically sharpening the s-Hamiltonian index bound
• Upper bound to the expectation value of the squared Hamiltonian
• The sum-of-squares hierarchy on the sphere and applications in quantum information theory
• Local optima of the Sherrington-Kirkpatrick Hamiltonian
• Quadratic quantum Hamiltonians revisited
• Quasi-exactly solvable quartic Bose Hamiltonians

Cites work

• A nearly tight sum-of-squares lower bound for the planted clique problem
• A Note on Extreme Correlation Matrices
• Adaptive estimation of a quadratic functional by model selection.
• Extremal cuts of sparse random graphs
• Following the Ground States of <scp>Full‐RSB</scp> Spherical Spin Glasses
• Geometry of cuts and metrics
• Global optimization with polynomials and the problem of moments
• scientific article; zbMATH DE number 48230 (Why is no real title available?)
• scientific article; zbMATH DE number 7650426 (Why is no real title available?)
• Invertibility of random matrices: norm of the inverse
• Lifting sum-of-squares lower bounds: degree-2 to degree-4
• Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
• Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective
• Multivariate normal approximation using exchangeable pairs
• On the bit complexity of sum-of-squares proofs
• On the existence of equiangular tight frames
• Probability in Banach spaces. Isoperimetry and processes
• Reducibility among combinatorial problems
• Semidefinite Optimization and Convex Algebraic Geometry
• Semidefinite programs on sparse random graphs and their application to community detection
• SOS is not obviously automatizable, even approximately
• Sparse sums of squares on finite abelian groups and improved semidefinite lifts
• Spectral norm of products of random and deterministic matrices
• Sum-of-squares proofs and the quest toward optimal algorithms
• Sums of squares, moment matrices and optimization over polynomials
• The algorithmic hardness threshold for continuous random energy models
• The concentration of measure phenomenon
• The Littlewood-Offord problem and invertibility of random matrices
• The Parisi formula
• The Parisi ultrametricity conjecture
• The Sherrington-Kirkpatrick model

Cited in

(8)

• Optimization of mean-field spin glasses
• On the integrality gap of degree-4 sum of squares for planted clique
• On the integrality gap of degree-4 sum of squares for planted clique
• Sum-of-squares certificates for maxima of random tensors on the sphere
• Disordered systems insights on computational hardness
• Asymptotically sharpening the s-Hamiltonian index bound
• The Spectrum of the Grigoriev–Laurent Pseudomoments
• Local geometry determines global landscape in low-rank factorization for synchronization

This page was built for publication: A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2235162)