Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 31 min ago
Peer-reviewedCC BYJournal of the European Mathematical Society

Moser–Tardos Algorithm with small number of random bits

  • Endre Csóka1
  • Łukasz Grabowski2
  • András Máthé3
  • Oleg Pikhurko3
  • Konstantinos Tyros4
4 affiliations
  1. 1Alfréd Rényi Institute of Mathematics, Budapest, Hungary
  2. 2Leipzig University, Germany
  3. 3University of Warwick, Coventry, UK
  4. 4National and Kapodistrian University of Athens, Greece
Open at sourceDOICite

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 subexponential growth, then the expected total number of random bits used by the algorithm is constant; in particular, it is independent of 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.

Related

  1. Lehto-type growth conditions and a Picard theorem for the gradient of entire solutions to the Euler -- Lagrange equations of variational integrals with linear growth in the plane including a small extension of Moser's Bernstein result
    Martin Fuchs
    arXivPreprintCC0Full textAnalysis & PDEsarXiv
  2. Approximation algorithm for mixed volumes of a constant number of convex bodies
    Hariharan Narayanan
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv
  3. Selecting the number of components in PCA via random signflips
    David Ke Hong, Yue Sheng, Edgar Dobriban
    Journal of the American Statistical AssociationPeer-reviewedLicence not statedFull text21 citedStatisticsOpenAlex
  4. An Island-Based Parallel Biased Random-Key Genetic Algorithm for the Three-Dimensional Trailer Loading Problem
    A. del Río, L. Díaz, L. C. de Vicente +2
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  5. Common random number simulation as the optimal coordinatewise coupling for iterated random functions
    Sabrina Sixta, Jeffrey S. Rosenthal
    arXivPreprintarXiv licenceFull textStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@article{csoka2026mosertardos,
  title = {{Moser–Tardos Algorithm with small number of random bits}},
  author = {Endre Csóka and Łukasz Grabowski and András Máthé and Oleg Pikhurko and Konstantinos Tyros},
  journal = {Journal of the European Mathematical Society},
  year = {2026},
  month = sep,
  doi = {10.4171/jems/1815},
  url = {https://doi.org/10.4171/jems/1815},
  note = {CC BY},
}
RIS
TY  - JOUR
TI  - Moser–Tardos Algorithm with small number of random bits
AU  - Endre Csóka
AU  - Łukasz Grabowski
AU  - András Máthé
AU  - Oleg Pikhurko
AU  - Konstantinos Tyros
PY  - 2026
DA  - 2026/09/25
JO  - Journal of the European Mathematical Society
DO  - 10.4171/jems/1815
UR  - https://doi.org/10.4171/jems/1815
AB  - 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 of 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.
SN  - 1435-9855
SN  - 1435-9863
ER  -