On the Complexity of Random Satisfiability Problems with Planted Solutions

Vitaly Feldman, Will Perkins, Santosh Vempala

The problem of identifying a planted assignment given a random $k$-SAT formula consistent with the assignment exhibits a large algorithmic gap: while the planted solution becomes u…