ECCC-Report TR14-148https://eccc.weizmann.ac.il/report/2014/148Comments and Revisions published for TR14-148en-usFri, 15 Jan 2016 20:07:06 +0200
Revision 1
| On the Complexity of Random Satisfiability Problems with Planted Solutions |
Vitaly Feldman,
Will Perkins,
Santosh Vempala
https://eccc.weizmann.ac.il/report/2014/148#revision1We consider the problem of identifying a planted assignment given a random $k$-SAT formula consistent with the assignment. This problem exhibits a large algorithmic gap: while the planted solution can always 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 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 \leq r \leq k$ for any distribution with a planted assignment).
Our main result is an unconditional lower bound, tight up to logarithmic factors, of $\tilde\Omega(n^{r/2})$ clauses for statistical (query) algorithms, matching the known upper bound (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 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 (2002) refutation hypothesis 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 (2000) one-way function and the associated pseudorandom generator when used with a sufficiently hard predicate. Fri, 15 Jan 2016 20:07:06 +0200https://eccc.weizmann.ac.il/report/2014/148#revision1
Paper TR14-148
| On the Complexity of Random Satisfiability Problems with Planted Solutions |
Vitaly Feldman,
Will Perkins,
Santosh Vempala
https://eccc.weizmann.ac.il/report/2014/148We consider the problem of identifying a planted assignment given a random $k$-SAT formula consistent with the assignment. This problem exhibits a large algorithmic gap: while the planted solution can always 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 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 \leq r \leq k$ for any distribution with a planted assignment).
Our main result is an unconditional lower bound, tight up to logarithmic factors, of $\tilde\Omega(n^{r/2})$ clauses for statistical algorithms, matching the known upper bound (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 algorithms. It also points to a geometric paring phenomenon in the space of all planted assignments that might be of independent interest.
As a consequence, we prove that a strong form of Feige's refutation hypothesis holds for statistical algorithms. Our bounds extend to the planted $k$-CSP model, defined by Goldreich as a candidate for one-way function, and therefore provide concrete evidence for the security of Goldreich's one-way function and the associated pseudorandom generator when used with a sufficiently hard predicate.Sat, 08 Nov 2014 11:35:17 +0200https://eccc.weizmann.ac.il/report/2014/148