论文标题
迈向洛瓦斯斯本地引理
Towards the sampling Lovász Local Lemma
论文作者
论文摘要
令$φ=（v，\ mathcal {c}）$是变量上的约束满意度问题，$ v_1，\ dots，v_n $，使每个约束都取决于最多$ k $变量，因此每个变量最多在大小$ [q] $的字母内假设值。假设每个约束最多都会与$δ$约束，并且每个约束最多都违反了$ p $的概率（在其变量上的产品度量下）。我们表明，对于$ k，q = o（1）$，有一种确定性的多项式时间算法，大约计算令人满意的作业数和一个随机的，多项式的时间算法，以大约从满足分配的均匀分布中进行样品，但前提是，前提是\ [c \ cdot q^{3} \ cdot cd^cd^cd^cd^cd^cd^^cd pot poc cd pot poc cd^cd^cd pot poc cd pot poc cd. \ quad \ text {其中} c \ text {是一个绝对常数。} \]之前，此形式的结果仅在特殊情况下才知道，当每个约束恰好违反其变量的一个分配时。 对于$ k $ -cnf公式的特殊情况，$δ^{7} $改善了以前最著名的$δ^{60} $用于确定性算法[Moitra，j.acm，2019]和$δ^{13} $的随机算法[Feng等[Feng et al。，Arxiv，2020]。对于适当的$ q $ - 颜色$ k $均匀的超图的特殊情况，术语$δ^{7} $改善了以前最著名的$Δ^{14} $用于确定性算法[Guo等，Sicomp，sicomp，2019]和$δ^{9} $ for Algolibled Algorithms algorithms al。
Let $Φ= (V, \mathcal{C})$ be a constraint satisfaction problem on variables $v_1,\dots, 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 $p$ (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\cdot q^{3}\cdot k \cdot p \cdot Δ^{7} < 1, \quad \text{where }C \text{ 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 $Δ^{7}$ improves the previously best known $Δ^{60}$ for deterministic algorithms [Moitra, J.ACM, 2019] and $Δ^{13}$ for randomized algorithms [Feng et al., arXiv, 2020]. For the special case of properly $q$-coloring $k$-uniform hypergraphs, the term $Δ^{7}$ improves the previously best known $Δ^{14}$ for deterministic algorithms [Guo et al., SICOMP, 2019] and $Δ^{9}$ for randomized algorithms [Feng et al., arXiv, 2020].
