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

We show that, if W ∈ ℝN × N_mathsfsym 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 · x^top W x under the constraints xi2 - 1 = 0 (i.e. x ∈ ± 1 N) that is asymptotically smaller than λmax(W) ≈ 2. We also conjecture a proof technique for lower bounds against sum-of-squares relaxations of any degree held constant as N → ∞, by proposing an approximate pseudomoment construction.