All reports by Author Will Perkins:

__
TR14-148
| 8th November 2014
__

Vitaly Feldman, Will Perkins, Santosh Vempala#### On the Complexity of Random Satisfiability Problems with Planted Solutions

Revisions: 1

Vitaly Feldman, Will Perkins, Santosh Vempala

We consider the problem of identifying a planted assignment given a random $k$-SAT formula consistent with the assignment. This problem 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 ... more >>>