论文标题
在本地引理制度中采样约束满意度解决方案
Sampling Constraint Satisfaction Solutions in the Local Lemma Regime
论文作者
论文摘要
我们给出了基于马尔可夫链的算法，用于对约束满意度问题（CSP）的几乎均匀解决方案进行采样。假设Lovász本地引理的规范设置，其中每个约束都被少数禁止的本地配置所违反，那么我们的采样算法在本地引理式中是准确的，并且运行时间是固定的多项式，其对$ n $的依赖性接近线性，其中$ n $ n $ n $ n $ n as $ n $是变量的数量。我们的主要方法是一种称为状态压缩的新技术，它概括了Moitra的“ Mark/Unmark”范式（Moitra，JACM，2019年），并且可以提供快速的基于本地 - 诱因的采样算法。作为我们技术的混凝土应用，我们为超图颜色和CNF溶液提供当前最佳的几乎均匀的采样器。
We give a Markov chain based algorithm for sampling almost uniform solutions of constraint satisfaction problems (CSPs). Assuming a canonical setting for the Lovász local lemma, where each constraint is violated by a small number of forbidden local configurations, our sampling algorithm is accurate in a local lemma regime, and the running time is a fixed polynomial whose dependency on $n$ is close to linear, where $n$ is the number of variables. Our main approach is a new technique called state compression, which generalizes the "mark/unmark" paradigm of Moitra (Moitra, JACM, 2019), and can give fast local-lemma-based sampling algorithms. As concrete applications of our technique, we give the current best almost-uniform samplers for hypergraph colorings and for CNF solutions.
