期刊
JOURNAL OF THE ACM
卷 68, 期 6, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3469832
关键词
Markov chain monte carlo; lovasz local lemma; k-SAT; approximate counting
类别
资金
- National Key R&D Program of China [2018YFB1003202]
- NSFC [61902241]
- European Research Council (ERC) under the European Union [947778]
- European Research Council (ERC) [947778] Funding Source: European Research Council (ERC)
The research introduces a new algorithm based on Markov chains for sampling and approximate counting of CNF formulas that meet certain conditions, achieving faster running times by bypassing connectivity barriers in traditional methods.
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 < n degrees((1)) and k >= 20 log k + 20 log d + 60, the new sampling algorithm runs in close to linear time, and the counting algorithm runs in close to quadratic time. Our approach is inspired by Moitra (JACM, 2019), which remarkably utilizes the Lowisz local lemma in approximate counting. Our main technical contribution is to use the local lemma to bypass the connectivity barrier in traditional Markov chain approaches, which makes the well-developed MCMC method applicable on disconnected state spaces such as SAT solutions. The benefit of our approach is to avoid the enumeration of local structures and obtain fixed polynomial running times, even if k = omega(1) or d = omega(1).
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据