Fast sampling and counting k-SAT solutions in the local lemma regime

2019/11/04 by Feng, Weiming, Guo, Heng, Yin, Yitong +1 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1911.01319

Abstract

We give new algorithms based on Markov chains to sample and approximately count satisfying assignments to k-uniform CNF formulas where each variable appears at most d times. For any k and d satisfying kd

Cited by

• Learning CNF formulas from uniform random solutions in the local lemma regime

Related

• Learning CNF formulas from uniform random solutions in the local lemma regime
• Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems
• The Local Lemma is asymptotically tight for SAT
• An Improved Algorithm for Sparse Instances of SAT
• An Approximation Algorithm for #k-SAT