  For a $k$-ary predicate $P$, a random instance of CSP$(P)$ with $n$ variables
and $m$ constraints is unsatisfiable with high probability when $m \gg n$. The
natural algorithmic task in this regime is \emph{refutation}: finding a proof
that a given random instance is unsatisfiable. Recent work of Allen et al.
suggests that the difficulty of refuting CSP$(P)$ using an SDP is determined by
a parameter $\mathrm{cmplx}(P)$, the smallest $t$ for which there does not
exist a $t$-wise uniform distribution over satisfying assignments to $P$. In
particular they show that random instances of CSP$(P)$ with $m \gg
n^{\mathrm{cmplx(P)}/2}$ can be refuted efficiently using an SDP.
  In this work, we give evidence that $n^{\mathrm{cmplx}(P)/2}$ constraints are
also \emph{necessary} for refutation using SDPs. Specifically, we show that if
$P$ supports a $(t-1)$-wise uniform distribution over satisfying assignments,
then the Sherali-Adams$_+$ and Lov\'{a}sz-Schrijver$_+$ SDP hierarchies cannot
refute a random instance of CSP$(P)$ in polynomial time for any $m \leq
n^{t/2-\epsilon}$.
