On the complexity of random satisfiability problems with planted solutions

For a planted satisfiability problem on n variables with k variables per constraint, the planted assignment becomes the unique solution after O(n log n) random clauses. However, the best-known algorithms need at least nr/2 to efficiently identify any assignment weakly correlated with the planted one for clause distributions that are (r − 1)-wise independent (r can be as high as k). Our main result is an unconditional lower bound, tight up to logarithmic factors, of Ω̃(nr/2) clauses for statistical algorithms, a broad class of algorithms introduced in [50, 34]. We complement this with a nearly matching upper bound using a statistical algorithm. As known approaches for problems over distributions in general, and planted satisfiability problems in particular, all have statistical analogues (spectral, MCMC, gradient-based, convex optimiza-tion etc.), this provides a rigorous explanation of the large gap between the identifiability and algorithmic identifiability thresholds for random satisfiability problems with planted solutions. Our results imply that a strong form of Feige’s refutation hypothesis for average-case SAT instances [31] holds for statistical algorithms. We also consider the closely related problem of finding the planted assignment of a random planted k-CSP which is the basis of Goldreich’s proposed one-way function [41]. Our bounds extend to this problem and give concrete evidence for the security of the one-way function and the associated pseudorandom generator when used with a sufficiently hard predicate