  Let $P:\{0,1\}^k \to \{0,1\}$ be a nontrivial $k$-ary predicate. Consider a
random instance of the constraint satisfaction problem $\mathrm{CSP}(P)$ on $n$
variables with $\Delta n$ constraints, each being $P$ applied to $k$ randomly
chosen literals. Provided the constraint density satisfies $\Delta \gg 1$, such
an instance is unsatisfiable with high probability. The \emph{refutation}
problem is to efficiently find a proof of unsatisfiability.
  We show that whenever the predicate $P$ supports a $t$-\emph{wise uniform}
probability distribution on its satisfying assignments, the sum of squares
(SOS) algorithm of degree $d = \Theta(\frac{n}{\Delta^{2/(t-1)} \log \Delta})$
(which runs in time $n^{O(d)}$) \emph{cannot} refute a random instance of
$\mathrm{CSP}(P)$. In particular, the polynomial-time SOS algorithm requires
$\widetilde{\Omega}(n^{(t+1)/2})$ constraints to refute random instances of
CSP$(P)$ when $P$ supports a $t$-wise uniform distribution on its satisfying
assignments. Together with recent work of Lee et al. [LRS15], our result also
implies that \emph{any} polynomial-size semidefinite programming relaxation for
refutation requires at least $\widetilde{\Omega}(n^{(t+1)/2})$ constraints.
  Our results (which also extend with no change to CSPs over larger alphabets)
subsume all previously known lower bounds for semialgebraic refutation of
random CSPs. For every constraint predicate~$P$, they give a three-way hardness
tradeoff between the density of constraints, the SOS degree (hence running
time), and the strength of the refutation. By recent algorithmic results of
Allen et al. [AOW15] and Raghavendra et al. [RRS16], this full three-way
tradeoff is \emph{tight}, up to lower-order factors.
