2018/01/10 by Rocco A. Servedio, Servedio, Rocco A., Li-Yang Tan +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1801.03588
openalex publication_date 2018/01/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ε 2n satisfying assignments, runs in time n^O(loglog n)2 for ε ≥ 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Ω(log n) even for constant ε. Our approach is based on a new general framework relating deterministic search and deterministic approximate counting, which we believe may find further applications.