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

DOI10.1007/S10107-020-01558-2zbMATH Open1478.90081arXiv1907.11686OpenAlexW3095481223MaRDI QIDQ2235162FDOQ2235162

Authors: Dmitriy Kunisky, Afonso S. Bandeira 

Publication date: 20 October 2021

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

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.

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

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

zbMATH Keywords

convex optimizationsemidefinite programmingsum-of-squaresspin glassaverage-case computational complexity

Mathematics Subject Classification ID

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

Cites Work

• Probability in Banach spaces. Isoperimetry and processes
• Adaptive estimation of a quadratic functional by model selection.
• The concentration of measure phenomenon
• Reducibility among combinatorial problems
• Global optimization with polynomials and the problem of moments
• Sums of squares, moment matrices and optimization over polynomials
• Sum-of-squares proofs and the quest toward optimal algorithms
• Semidefinite Optimization and Convex Algebraic Geometry
• Multivariate normal approximation using exchangeable pairs
• On the existence of equiangular tight frames
• The Parisi ultrametricity conjecture
• The Parisi formula
• The Sherrington-Kirkpatrick model
• Geometry of cuts and metrics
• Spectral norm of products of random and deterministic matrices
• The Littlewood-Offord problem and invertibility of random matrices
• A Note on Extreme Correlation Matrices
• Invertibility of random matrices: norm of the inverse
• Sparse sums of squares on finite abelian groups and improved semidefinite lifts
• Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
• Title not available (Why is that?)
• Semidefinite programs on sparse random graphs and their application to community detection
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• Extremal cuts of sparse random graphs
• Title not available (Why is that?)
• SOS is not obviously automatizable, even approximately
• Following the Ground States of <scp>Full‐RSB</scp> Spherical Spin Glasses
• On the bit complexity of sum-of-squares proofs
• The algorithmic hardness threshold for continuous random energy models
• 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

Cited In (7)

• 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
• The Spectrum of the Grigoriev–Laurent Pseudomoments
• Optimization of mean-field spin glasses
• On the integrality gap of degree-4 sum of squares for planted clique
• Disordered systems insights on computational hardness
• Asymptotically sharpening the $s$-Hamiltonian index bound

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)