Moser-Tardos Algorithm with small number of random bits
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914503757660160 |
|---|---|
| author | Csóka, Endre Grabowski, Łukasz Máthé, András Pikhurko, Oleg Tyros, Konstantinos |
| author_facet | Csóka, Endre Grabowski, Łukasz Máthé, András Pikhurko, Oleg Tyros, Konstantinos |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2203_05888 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Moser-Tardos Algorithm with small number of random bits Csóka, Endre Grabowski, Łukasz Máthé, András Pikhurko, Oleg Tyros, Konstantinos Combinatorics Distributed, Parallel, and Cluster Computing Data Structures and Algorithms Logic 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. |
| title | Moser-Tardos Algorithm with small number of random bits |
| topic | Combinatorics Distributed, Parallel, and Cluster Computing Data Structures and Algorithms Logic |
| url | https://arxiv.org/abs/2203.05888 |