论文标题
带有少量随机位的Moser-Tardos算法
Moser-Tardos Algorithm with small number of random bits
论文作者
论文摘要
我们研究了平行Moser-Tardos算法的变体。我们证明，如果我们将注意力限制在依赖图具有亚指数增长的一类问题，那么算法使用的预期随机位数是恒定的。特别是，它与变量的数量独立。这是通过使用相同的随机位来重新采样变量来实现的，而变量在依赖图图中足够远。 有两个推论。首先，我们获得了用于查找令人满意的分配的确定性算法，对于任何类别的问题，如前一段中，该算法在时间o（n）中运行，其中n是变量的数量。其次，我们提出了Lovász本地引理的Borel版本。
We study a variant of the parallel Moser-Tardos Algorithm. We prove that if we restrict attention to a class of problems whose dependency graphs have subexponential growth, then the expected total number of random bits used by the algorithm is constant; in particular, it is independent from the number of variables. This is achieved by using the same random bits to resample variables which are far enough in the dependency graph. There are two corollaries. First, we obtain a deterministic algorithm for finding a satisfying assignment, which for any class of problems as in the previous paragraph runs in time O(n), where n is the number of variables. Second, we present a Borel version of the Lovász Local Lemma.
