  The Sum-of-Squares (SoS) hierarchy is a semi-definite programming
meta-algorithm that captures state-of-the-art polynomial time guarantees for
many optimization problems such as Max-$k$-CSPs and Tensor PCA. On the flip
side, a SoS lower bound provides evidence of hardness, which is particularly
relevant to average-case problems for which NP-hardness may not be available.
  In this paper, we consider the following average case problem, which we call
the \emph{Planted Affine Planes} (PAP) problem: Given $m$ random vectors
$d_1,\ldots,d_m$ in $\mathbb{R}^n$, can we prove that there is no vector $v \in
\mathbb{R}^n$ such that for all $u \in [m]$, $\langle v, d_u\rangle^2 = 1$? In
other words, can we prove that $m$ random vectors are not all contained in two
parallel hyperplanes at equal distance from the origin? We prove that for $m
\leq n^{3/2-\epsilon}$, with high probability, degree-$n^{\Omega(\epsilon)}$
SoS fails to refute the existence of such a vector $v$.
  When the vectors $d_1,\ldots,d_m$ are chosen from the multivariate normal
distribution, the PAP problem is equivalent to the problem of proving that a
random $n$-dimensional subspace of $\mathbb{R}^m$ does not contain a boolean
vector. As shown by Mohanty--Raghavendra--Xu [STOC 2020], a lower bound for
this problem implies a lower bound for the problem of certifying energy upper
bounds on the Sherrington-Kirkpatrick Hamiltonian, and so our lower bound
implies a degree-$n^{\Omega(\epsilon)}$ SoS lower bound for the certification
version of the Sherrington-Kirkpatrick problem.
