A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian
share
We show that, if W∈R^N × N_sym 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^Wx under the constraints x_i^2 - 1 = 0 (i.e. x∈{± 1 }^N) that is asymptotically smaller than λ_(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.
READ FULL TEXT