  We show that, if $\mathbf{W} \in \mathbb{R}^{N \times N}_{\mathsf{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} \cdot \mathbf{x}^\top \mathbf{W} \mathbf{x}$ 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.
