论文标题
在接近线性的时间内采样lovász局部引理，以进行一般约束满意度解决方案
Sampling Lovász Local Lemma For General Constraint Satisfaction Solutions In Near-Linear Time
论文作者
论文摘要
我们给出了一种快速算法，用于在局部引理状态下对一般约束满意度问题（CSP）进行均匀的解决方案采样。假设CSP具有$ n $变量具有域大小的$ n $变量，每个约束最多包含k变量，最多与$δ$约束共享变量，并且由均匀的随机分配违反了最多概率的概率。该算法在预期的$ \ mathrm {poly}（q，k，Δ）\ cdot \ tilde {o}（n）$时间（只要局部lemma条件得到满足： } C_0。 \]以前，在类似的局部引理条件下，在$ n $和$δ$中使用运行时间多项式的采样算法仅因几乎是原子质而闻名，在这种情况下，每个约束都被少数禁止的本地配置所违反。在我们本地的引理状态下的关键术语$δ^5 $也改善了一般CSP [JPV21B]的先前最著名的$δ^7 $和原子CSP的$δ^{5.714} $，包括$ k $ -CNF的特殊案例[JPV21A，HSW21]。 我们的抽样方法与以前的快速算法相反，用于采样LLL，这些算法基于马尔可夫链。我们算法的关键步骤是具有独立利益的递归边缘采样器。在局部引理状态下，该边缘采样器可以根据其边缘分布的变量绘制随机值，其成本与CSP的大小无关。
We give a fast algorithm for sampling uniform solutions of general constraint satisfaction problems (CSPs) in a local lemma regime. Suppose that the CSP has $n$ variables with domain size at most q, each constraint contains at most k variables, shares variables with at most $Δ$ constraints, and is violated with probability at most $p$ by a uniform random assignment. The algorithm returns an almost uniform satisfying assignment in expected $\mathrm{poly}(q,k,Δ)\cdot\tilde{O}(n)$ time, as long as a local lemma condition is satisfied: \[ k\cdot p\cdot q^2\cdot Δ^5\le C_0\quad\text{for a suitably small absolute constant }C_0. \] Previously, under similar local lemma conditions, sampling algorithms with running time polynomial in both $n$ and $Δ$ were only known for the almost atomic case, where each constraint is violated by a small number of forbidden local configurations. The key term $Δ^5$ in our local lemma condition also improves the previously best known $Δ^7$ for general CSPs [JPV21b] and $Δ^{5.714}$ for atomic CSPs, including the special case of $k$-CNF [JPV21a, HSW21]. Our sampling approach departs from previous fast algorithms for sampling LLL, which were based on Markov chains. A crucial step of our algorithm is a recursive marginal sampler that is of independent interests. Within a local lemma regime, this marginal sampler can draw a random value for a variable according to its marginal distribution, at a cost independent of the size of the CSP.
