3.8 Proceedings Paper

Towards the sampling Lovasz Local Lemma

出版社

IEEE COMPUTER SOC
DOI: 10.1109/FOCS52979.2021.00025

关键词

Lovasz Local Lemma; counting; sampling

向作者/读者索取更多资源

This study introduces a new algorithm for solving constraint satisfaction problems, capable of accurately calculating the number of satisfying assignments and sampling from approximately uniform distributions. The algorithm outperforms previous best known algorithms in several specific cases.
Let Phi = (V, C) be a constraint satisfaction problem on variables v(1), ..., v(n) such that each constraint depends on at most k variables and such that each variable assumes values in an alphabet of size at most [q]. Suppose that each constraint shares variables with at most. constraints and that each constraint is violated with probability at most Delta (under the product measure on its variables). We show that for k, q = O(1), there is a deterministic, polynomial time algorithm to approximately count the number of satisfying assignments and a randomized, polynomial time algorithm to sample from approximately the uniform distribution on satisfying assignments, provided that C.q(2).k.p.Delta(7) < 1, where C is an absolute constant. Previously, a result of this form was known essentially only in the special case when each constraint is violated by exactly one assignment to its variables. For the special case of k-CNF formulas, the term Delta(7) improves the previously best known Delta(60) for deterministic algorithms [Moitra, J.ACM, 2019] and Delta(13) for randomized algorithms [Feng, Guo, Yin, and Zhang, STOC 2021]. For the special case of properly q-coloring k-uniform hypergraphs, the term Delta(7) improves the previously best known Delta(14) for deterministic algorithms [Guo, Liao, Lu, and Zhang, SICOMP, 2019] and Delta(9) for randomized algorithms [Feng, Guo, Yin, and Zhang, STOC 2021].

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

3.8
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据