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

arXiv: https://arxiv.org/abs/1907.11686 · HTML: https://mlsanity.com/paper/1907.11686/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jul 2019.

## Built on by (most cited first, 3 of 3)

- [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021)
- [Clustering a Mixture of Gaussians with Unknown Covariance](https://mlsanity.com/paper/2110.01602/) (2021)
- [Semidefinite programs simulate approximate message passing robustly](https://mlsanity.com/paper/2311.09017/) (2023)

## Abstract (arXiv)

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.