  Let $P$ be a $k$-ary predicate over a finite alphabet. Consider a random
CSP$(P)$ instance $I$ over $n$ variables with $m$ constraints. When $m \gg n$
the instance $I$ will be unsatisfiable with high probability, and we want to
find a refutation - i.e., a certificate of unsatisfiability. When $P$ is the
$3$-ary OR predicate, this is the well studied problem of refuting random
$3$-SAT formulas, and an efficient algorithm is known only when $m \gg
n^{3/2}$. Understanding the density required for refutation of other predicates
is important in cryptography, proof complexity, and learning theory.
Previously, it was known that for a $k$-ary predicate, having $m \gg n^{\lceil
k/2 \rceil}$ constraints suffices for refutation. We give a criterion for
predicates that often yields efficient refutation algorithms at much lower
densities. Specifically, if $P$ fails to support a $t$-wise uniform
distribution, then there is an efficient algorithm that refutes random CSP$(P)$
instances $I$ whp when $m \gg n^{t/2}$. Indeed, our algorithm will "somewhat
strongly" refute $I$, certifying $\mathrm{Opt}(I) \leq 1-\Omega_k(1)$, if $t =
k$ then we get the strongest possible refutation, certifying $\mathrm{Opt}(I)
\leq \mathrm{E}[P] + o(1)$. This last result is new even in the context of
random $k$-SAT. Regarding the optimality of our $m \gg n^{t/2}$ requirement,
prior work on SDP hierarchies has given some evidence that efficient refutation
of random CSP$(P)$ may be impossible when $m \ll n^{t/2}$. Thus there is an
indication our algorithm's dependence on $m$ is optimal for every $P$, at least
in the context of SDP hierarchies. Along these lines, we show that our
refutation algorithm can be carried out by the $O(1)$-round SOS SDP hierarchy.
Finally, as an application of our result, we falsify assumptions used to show
hardness-of-learning results in recent work of Daniely, Linial, and
Shalev-Shwartz.
