pith. sign in

arxiv: 2203.05888 · v3 · submitted 2022-03-11 · 🧮 math.CO · cs.DC· cs.DS· math.LO

Moser-Tardos Algorithm with small number of random bits

Endre Cs\'oka , {\L}ukasz Grabowski , Andr\'as M\'ath\'e , Oleg Pikhurko , Konstantinos Tyros This is my paper

Pith reviewed 2026-05-24 12:04 UTC · model grok-4.3

classification 🧮 math.CO cs.DCcs.DSmath.LO
keywords Moser-Tardos algorithmLovász Local Lemmarandom bitssubexponential growthdependency graphBorel combinatoricsderandomizationsatisfying assignment
0
0 comments X

The pith

By reusing random bits for distant variables, a variant of the Moser-Tardos algorithm uses only a constant expected number of bits independent of the number of variables when dependency graphs have subexponential growth.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that a parallel variant of the Moser-Tardos algorithm, modified to reuse identical random bits when resampling variables separated by sufficient distance in the dependency graph, keeps the total expected number of random bits bounded by a constant. This bound holds for any collection of problems whose dependency graphs exhibit subexponential growth and does not grow with the total number of variables. The result immediately supplies a deterministic linear-time procedure that outputs a satisfying assignment and also yields a Borel formulation of the Lovász Local Lemma.

Core claim

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.

What carries the argument

Reusing the same random bits to resample variables which are far enough in the dependency graph.

If this is right

  • The expected number of random bits remains bounded by a constant independent of the number of variables.
  • A deterministic algorithm finds a satisfying assignment in O(n) time.
  • A Borel version of the Lovász Local Lemma holds for the same class of problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The bit-reuse technique may transfer to other resampling-based algorithms that operate on graphs with controlled growth.
  • Linear-time deterministic solvers become available for large-scale instances once the growth condition is verified.
  • The construction supplies a route from algorithmic local lemma results to statements in measurable graph theory without additional randomness assumptions.

Load-bearing premise

The dependency graphs of the input problems have subexponential growth.

What would settle it

A concrete family of Lovász Local Lemma instances whose dependency graphs have subexponential growth yet require an unbounded expected number of distinct random bits even after optimal reuse at large distances.

Figures

Figures reproduced from arXiv: 2203.05888 by Andr\'as M\'ath\'e, Endre Cs\'oka, Konstantinos Tyros, {\L}ukasz Grabowski, Oleg Pikhurko.

Figure 2
Figure 2. Figure 2: The forest from Figure [PITH_FULL_IMAGE:figures/full_fig_p023_2.png] view at source ↗
read the original 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 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\'asz Local Lemma.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript studies a variant of the parallel Moser-Tardos algorithm. It proves that, when the dependency graph has subexponential growth, the expected number of distinct random bits consumed by the algorithm is bounded by a constant independent of the number of variables n; this is obtained by reusing the same random bits for variables at sufficient distance in the graph. Two corollaries are stated: a deterministic O(n)-time algorithm for finding a satisfying assignment, and a Borel version of the Lovász Local Lemma.

Significance. If the central claim holds, the result supplies a concrete randomness-reduction technique for the MT algorithm on a natural and broad class of LLL instances. The deterministic linear-time corollary and the Borel extension are direct, standard consequences once a constant-bit source is available. The approach of distance-based bit reuse, combined with the growth hypothesis to bound the number of distinct sources, is a clean contribution to algorithmic LLL literature.

minor comments (2)
  1. The abstract states that bits are reused 'far enough' but does not indicate the precise distance threshold or the coloring argument used to select the reuse pattern; a one-sentence clarification would help readers locate the key technical step.
  2. The growth condition is invoked to bound the number of distinct bit sources, yet the manuscript does not appear to record an explicit functional dependence of the constant on the growth function; adding this dependence (even asymptotically) would strengthen the statement.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript, the assessment of its significance, and the recommendation of minor revision. The referee's description of the central claim, the bit-reuse technique under subexponential growth, and the two corollaries matches the paper exactly.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained under growth hypothesis

full rationale

The paper directly proves that subexponential growth of the dependency graph bounds the number of distinct random bit sources needed when bits are reused at fixed distance (via a coloring argument on the power graph), yielding a constant expected bit count independent of n. This follows from the explicit hypothesis without any fitted parameters renamed as predictions, self-definitional loops, or load-bearing self-citations that reduce the central claim to its own inputs. The deterministic O(n) and Borel LLL corollaries are standard consequences of a constant-bit source and do not introduce circularity. No equations or steps in the provided abstract or description exhibit reduction by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on the standard Moser-Tardos resampling framework and the Lovász Local Lemma existence guarantee, plus the domain restriction to subexponential growth. No free parameters or new entities are introduced in the abstract.

axioms (2)
  • domain assumption The Moser-Tardos resampling procedure correctly finds satisfying assignments when the LLL condition holds.
    The variant is built directly on the standard MT algorithm.
  • domain assumption Dependency graphs have subexponential growth.
    This is the explicit class restriction used to obtain the constant-bit bound.

pith-pipeline@v0.9.0 · 5674 in / 1405 out tokens · 25865 ms · 2026-05-24T12:04:19.900751+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

  1. [1]

    Bernshteyn, Measurable versions of the Lovász Local Lemma and measurable graph colorings, Adv

    A. Bernshteyn, Measurable versions of the Lovász Local Lemma and measurable graph colorings, Adv. Math. 353 (2019), 153–223

    work page 2019

  2. [2]

    , Distributed algorithms, the Lovász local lemma, and descriptive combinatorics, Invent. Math. 233 (2023), 495–542

    work page 2023

  3. [3]

    Math.415 (2023), Paper No

    , Probabilistic constructions in continuous combinatorics and a bridge to distributed algo- rithms, Adv. Math.415 (2023), Paper No. 108895, 33

    work page 2023

  4. [4]

    Bernshteyn and J

    A. Bernshteyn and J. Yu, Large-scale geometry of Borel graphs of polynomial growth, Eprint arXiv:2302.04727 (2023)

    work page arXiv 2023

  5. [5]

    Anton Bernshteyn and Felix Weilacher,Borel versions of the local lemma and local algorithms for graphs of finite asymptotic separation index, Eprint arXiv:2308.14941 (2023)

    work page arXiv 2023

  6. [6]

    Brandt, Y.-J

    S. Brandt, Y.-J. Chang, J. Grebík, C. Grunau, V. Rozhoň, and Z. Vidnyánszky,On homomorphism graphs, 2021. E-print arXiv:2111.03683

    work page arXiv 2021

  7. [7]

    Brandt, O

    S. Brandt, O. Fischer, J. Hirvonen, B. Keller, T. Lempiäinen, J. Rybicki, J. Suomela, and J. Uitto, A lower bound for the distributed Lovász local lemma, STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016, pp. 479–488. 30

    work page 2016

  8. [8]

    Chandrasekaran, N

    K. Chandrasekaran, N. Goyal, and B. Haeupler,Deterministic algorithms for the lovász local lemma, Proceedings of the twenty-first annual acm-siam symposium on discrete algorithms, 2010, pp. 992– 1004

    work page 2010

  9. [9]

    ,Deterministic algorithms for the lovász local lemma,SIAMJournalonComputing 42(2013), 2132–2155

    work page 2013

  10. [10]

    Chang and S

    Y.-J. Chang and S. Pettie,A time hierarchy theorem for theLOCAL model, SIAM J. Computing48 (2019), 33–69

    work page 2019

  11. [11]

    Conley, S

    C. Conley, S. Jackson, A. S. Marks, B. Seward, and R. Tucker-Drob,Hyperfiniteness and Borel combinatorics, J. Europ. Math. Soc22 (2020), 877–892

    work page 2020

  12. [12]

    C. T. Conley and O. Tamuz,Unfriendly colorings of graphs with finite average degree, Proc. London Math. Soc. 121 (2020), 828–832

    work page 2020

  13. [13]

    Csóka, Ł

    E. Csóka, Ł. Grabowski, A. Máthé, O. Pikhurko, and K.Tyros,Borel version of the local lemma,

    work page

  14. [14]

    E-print arXiv:1605.04877

    work page arXiv

  15. [15]

    Lovász,Problems and results on3-chromatic hypergraphs and some related questions, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P

    P.Erdős andL. Lovász,Problems and results on3-chromatic hypergraphs and some related questions, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, 1975, pp. 609–627. Colloq. Math. Soc. János Bolyai, Vol. 10

    work page 1973

  16. [16]

    Fischer and M

    M. Fischer and M. Ghaffari,Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy, 31 International Symposium on Distributed Computing, 2017, pp. Art. No. 18, 16

    work page 2017

  17. [17]

    Ghaffari, C

    M. Ghaffari, C. Grunau, and V. Rozhoň,Improved deterministic network decomposition, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021, pp. 2904–2923

    work page 2021

  18. [18]

    Grebík and V

    J. Grebík and V. Rozhoň,Classification of local problems on paths from the perspective of descriptive combinatorics, 2021. E-print arXiv:2103.14112

    work page arXiv 2021

  19. [19]

    Grebík and V

    J. Grebík and V. Rozhoň,Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics, Advances in Mathematics431 (2023), 109241

    work page 2023

  20. [20]

    A. S. Kechris and A. S. Marks,Descriptive graph combinatorics, 2020. Manuscript, 139pp, available at http://www.math.caltech.edu/~kechris/papers/combinatorics20book.pdf

    work page 2020

  21. [21]

    A. S. Kechris, S. Solecki, and S. Todorcevic,Borel chromatic numbers, Adv. Math.141 (1999), 1–44

    work page 1999

  22. [22]

    Kun, Expanders have a spanning Lipschitz subgraph with large girth , 2013

    G. Kun, Expanders have a spanning Lipschitz subgraph with large girth , 2013. E-print arXiv:1303.4982

    work page arXiv 2013

  23. [23]

    Linial,Locality in distributed graph algorithms, SIAM J

    N. Linial,Locality in distributed graph algorithms, SIAM J. Computing21 (1992), 193–201

    work page 1992

  24. [24]

    A. S. Marks,A determinacy approach to Borel combinatorics, J. Amer. Math. Soc.29 (2016), 579– 600

    work page 2016

  25. [25]

    R. A. Moser,A constructive proof of the Lovász local lemma, STOC’09—Proceedings of the 2009 ACM International Symposium on Theory of Computing, 2009, pp. 343–350

    work page 2009

  26. [26]

    R. A. Moser and G. Tardos,A constructive proof of the general Lovász local lemma, J. ACM 57 (2010), no. 2, Art. 11, 15

    work page 2010

  27. [27]

    Ch. H. Papadimitriou,Computational complexity., Addison-Wesley, 1994

    work page 1994

  28. [28]

    Pikhurko,Borel combinatorics of locally finite graphs, Surveys in combinatorics, 2021, pp

    O. Pikhurko,Borel combinatorics of locally finite graphs, Surveys in combinatorics, 2021, pp. 267– 319

    work page 2021

  29. [29]

    Rozhoň and M

    V. Rozhoň and M. Ghaffari,Polylogarithmic-time deterministic network decomposition and dis- tributed derandomization, STOC ’20—Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020, pp. 350–363

    work page 2020

  30. [30]

    J. H. Spencer,Robin Moser makes Lovász Local Lemma Algorithmic! Notes of Joel Spencer. Avail- able at https://www.cs.nyu.edu/spencer/moserlovasz1.pdf

    work page

  31. [31]

    1, 69–76

    , Asymptotic lower bounds for Ramsey functions, Discrete Math.20 (1977/78), no. 1, 69–76

    work page 1977

  32. [32]

    Thornton,Orienting Borel graphs, Proc

    R. Thornton,Orienting Borel graphs, Proc. Amer. Math. Soc.150 (2022), 1779–1793. 31

    work page 2022