The ACO Seminar (2013–2014)

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(n^k/2 ln n) and has the same time complexity; this bound was conjectured in the literature and previously known only for even k. In contrast, it is well-known that only O(n ln n) clauses suffice to identify the planted assignment (inefficiently). We consider lower bounds, and show that any statistical 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).