Moser-Tardos Algorithm with small number of random bits

arXiv2203.05888MaRDI QIDQ6505586FDOQ6505586

Authors: Endre Csóka, Łukasz Grabowski, András Máthé, Oleg Pikhurko, Konstantinos Tyros 

Abstract: 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 some fixed 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 colloraries. First, we obtain a deterministic algorithm for finding a satisfying assignment, which in 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'asz Local Lemma.

This page was built for publication: Moser-Tardos Algorithm with small number of random bits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6505586)