Łukasz Grabowski

Moser–Tardos Algorithm with small number of random bits

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 indep...