Moser-Tardos Algorithm with small number of random bits
For researchers in randomized algorithms and the Lovász Local Lemma, this provides a significant reduction in randomness and new deterministic and Borel results for a broad class of problems.
The paper proves that for problems with dependency graphs of subexponential growth, the parallel Moser-Tardos algorithm uses a constant expected number of random bits, independent of the number of variables. This yields a deterministic O(n)-time algorithm and a Borel version of the Lovász Local Lemma.
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.