Sep. 26, 3:30pm, Wean 8220

Santosh Vempala, Georgia Tech

On the Complexity of Random Problems with Planted Solutions

Santosh Vempala, Georgia Tech

On the Complexity of Random Problems with Planted Solutions

Abstract:

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).