On the Complexity of Random Satisfiability Problems with Planted Solutions

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 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 ≤ r ≤ k for any distribution with a planted assignment).

Authors

• Vitaly Feldman
• Will Perkins 0001
• Santosh S. Vempala

Keywords

• statistical algorithms
• planted satisfiability
• refutation
• hypergraph partitioning
• k-sat