A tight degree 4 sum-of-squares lower bound for the Sherrington–Kirkpatrick Hamiltonian
Dmitriy Kunisky, Afonso S. Bandeira · Mathematical Programming · 2020
We show that, if $${\varvec{W}}$$ is an $$N \times N$$ matrix 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 \varvec{x}^\top \varvec{W} \varvec{x}$$ under the constraints $$x_i^2 - 1 = 0$$ (i.e. $$\varvec{x}\in \{\pm 1 \}^N$$ ) that is asymptotically smaller than $$\lambda _{\max }({\varvec{W}}) \approx 2$$ . We also conjecture a proof technique for lower bounds against sum-of-squares relaxations of any degree held constant as $$N \rightarrow \infty $$ , by proposing an approximate pseudomoment construction.