  The problem of identifying a planted assignment given a random $k$-SAT
formula consistent with the assignment exhibits a large algorithmic gap: while
the planted solution becomes unique and can be identified given a formula with
$O(n\log n)$ clauses, there are distributions over clauses for which the best
known efficient algorithms require $n^{k/2}$ clauses. We propose and study a
unified model for planted $k$-SAT, which captures well-known special cases. An
instance is described by a planted assignment $\sigma$ and a distribution on
clauses with $k$ literals. We define its distribution complexity as the largest
$r$ for which the distribution is not $r$-wise independent ($1 \le r \le k$ for
any distribution with a planted assignment).
  Our main result is an unconditional lower bound, tight up to logarithmic
factors, for statistical (query) algorithms [Kearns 1998, Feldman et. al 2012],
matching known upper bounds, which, as we show, can be implemented using a
statistical algorithm. Since known approaches for problems over distributions
have statistical analogues (spectral, MCMC, gradient-based, convex optimization
etc.), this lower bound provides a rigorous explanation of the observed
algorithmic gap. The proof introduces a new general technique for the analysis
of statistical query algorithms. It also points to a geometric paring
phenomenon in the space of all planted assignments.
  We describe consequences of our lower bounds to Feige's refutation hypothesis
[Feige 2002] and to lower bounds on general convex programs that solve planted
$k$-SAT. Our bounds also extend to other planted $k$-CSP models, and, in
particular, provide concrete evidence for the security of Goldreich's one-way
function and the associated pseudorandom generator when used with a
sufficiently hard predicate [Goldreich 2000].
