ACO The ACO Seminar (2013–2014)

Sep. 26, 3:30pm, Wean 8220
Santosh Vempala, Georgia Tech
On the Complexity of Random Problems with Planted Solutions


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(nk/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).

Back to the ACO home page