Simpler Partial Derandomization of PPSZ for k-SAT

2020/01/17 by S. Cliff Liu, Liu, S. Cliff
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #F.2.2 #FOS: Computer and information sciences #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2001.06536

openalex publication_date 2020/01/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give a simpler derandomization of the best known k-SAT algorithm PPSZ [FOCS'97, JACM'05] for k-SAT with sub-exponential number of solutions. The existing derandomization uses a complicated construction of small sample space, while we only use hashing. Our algorithm and theorem also have a nice byproduct: It outperforms the current fastest deterministic k-SAT algorithm when the formula has moderately exponential number of solutions.

Citations

• Which Problems Have Strongly Exponential Complexity?
• Popular conjectures imply strong lower bounds for dynamic problems

Related

• A Full Derandomization of Schoening's k-SAT Algorithm
• 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
• Derandomizing HSSW Algorithm for 3-SAT
• Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT
• Super Strong ETH is False for Random k-SAT