December 7, 2016
We consider the fundamental derandomization problem of deterministically finding a satisfying assignment to a CNF formula that has many satisfying assignments. We give a deterministic algorithm which, given an n-variable poly(n)-clause CNF formula F that has $|F^{-1}(1)| \geq \epsilon 2^n$, runs in time $n^{\tilde{O}(\log\log n)^2}$ for $\epsilon \ge 1/\polylog(n)$ and outputs a satisfying assignment of F. Prior to our work the fastest known algorithm for this problem was simply to enumerate over all seeds of a pseudorandom generator for CNFs; using the best known PRGs for CNFs [DETT10], this takes time $n^{\tilde{\Omega}(\log n)}$ even for constant $\epsilon$. Joint work with Rocco Servedio.