A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian

Abstract

We show that, if $\mathbf{W}\in {\mathbb{R}}_{\mathsf{sym}}^{N\times N}$ 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}\cdot {\mathbf{x}}^{\top }\mathbf{Wx}$ under the constraints $x_i^2-1=0$ (i.e. $\mathbf{x}\in \{\pm 1{\}}^N$) that is asymptotically smaller than ${\lambda }_{\max }(\mathbf{W})\approx 2$. We also conjecture a proof technique for lower bounds against sum-of-squares relaxations of any degree held constant as $N\to \infty$, by proposing an approximate pseudomoment construction.

34 pages. Minor text revisions; closest to published version to appear in Mathematical Programming