Deterministic search for CNF satisfying assignments in almost polynomial time.
R. Servedio and L.-Y. Tan.
In 58th Annual Symposium on Foundations of Computer Science (FOCS), 2017, pp. 813--823.


Abstract:

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 at least $\eps 2^n$ satisfying assignments, runs in time $n^{\tilde{O}(\log\log n)^2} $for $\eps \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 \cite{DETT10}, this takes time $n^{\tilde{\Omega}(\log n)}$ even for constant $\eps$. Our approach is based on a new general framework relating deterministic search and deterministic approximate counting, which we believe may find further applications.

pdf


Back to main papers page