We consider the problem of finding a planted satisfying assignment of
a random k
-SAT formula, and its generalization to finding a planted partition in a random k
-uniform hypergraph. How many random clauses are needed?
We give an algorithm that uses O
) and has the same time complexity; this bound was conjectured in the literature and previously known only for
In contrast, it is well-known that only O(n
) clauses suffice to identify the
planted assignment (inefficiently). We consider lower bounds, and show that any
algorithm has a lower bound that matches our upper bound up to logarithmic factors. Known approaches to this problem can be viewed as
statistical algorithms, and so this appears to be the first rigorous explanation of the large gaps between the algorithmic and existential thresholds for
detecting planted solutions of satisfiability problems.
Joint work with Will Perkins (Gatech) and Vitaly Feldman (IBM).