Pith. sign in

REVIEW 3 major objections 5 minor 2 cited by

A Sharp Threshold Phenomenon for the Distributed Complexity of the Lov\'asz Local Lemma

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For the Lovász Local Lemma with variables affecting at most three events, a deterministic distributed algorithm runs in O(d^2 + log* n) rounds whenever p < 2^{-d}, making p = 2^{-d} a sharp threshold.

desk verdict A strong paper with a real but fixable algebraic error in a deferred proof; the rank-3 algorithm and threshold result deserve a serious referee. read the letter →

arxiv 1908.06270 v2 pith:TEID3PFW submitted 2019-08-17 cs.DS cs.DC

Sebastian Brandt , Yannic Maus , Jara Uitto This is my paper · ORCID
classification cs.DScs.DC MSC 68W1505D40
keywords LovászLocalLemmadistributedalgorithmsmodeldeterministicsharpthresholdprobabilisticmethodhypergraphorientationderandomization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper tries to pin down exactly when the Lovász Local Lemma (LLL) becomes easy to solve on a distributed network. It proves that for the case where each random variable influences at most two bad events, and then for the harder case of at most three events, the exponential criterion $p < 2^{-d}$ is a sharp threshold: below it there is a deterministic LOCAL algorithm that runs in $O(d + \log^* n)$ rounds (rank 2) or $O(d^2 + \log^* n)$ rounds (rank 3), matching the universal $\Omega(\log^* n)$ lower bound, while at $p \geq 2^{-d}$ the known $\Omega(\log \log n)$ randomized and $\Omega(\log n)$ deterministic lower bounds take over. Because the fixing process works in any adversarial order and only consults the 1-hop neighborhood, the result gives deterministic algorithms for concrete problems such as rank-3 hypergraph orientation. The paper also conjectures the same threshold holds for variables affecting any fixed number $r$ of events, and provides a proof framework where almost all steps already extend to arbitrary $r$.

What carries the argument

The engine is the Variable Fixing Lemma (Lemma 3.2), supported by a bookkeeping scheme called property $\mathcal{P}^*$. The algorithm maintains, on every edge of the dependency graph and for each endpoint, a value in $[0,2]$ whose product over the incident edges upper-bounds the conditional probability of that endpoint's bad event, and the values on any edge always sum to at most 2. When a rank-3 variable on hyperedge $\{u,v,w\}$ is fixed, the lemma guarantees a choice of value and an update of the six edge values that preserves $\mathcal{P}^*$. The geometric core is the set $S_{\mathrm{rep}}$ of representable triples $(a,b,c)$ -- triples of probability increases that can be absorbed by the three edges of a triangle -- which is characterized as the region under the surface $f(a,b) = 4 + \frac{1}{2}(ab - 2a - 2b - \sqrt{ab(4-a)(4-b)})$. The proof reduces existence of a good fixing choice to the incurredness of $S_{\mathrm{rep}}$ (no convex combination of two non-representable triples is representable), and incurredness is derived from convexity of $f$ on $\{a+b \le 4\}$, verified by a Hessian computation.

What would settle it

Recompute the Hessian matrix of $f$ at an interior point of $\{(a,b): a+b<4\}$ and check whether it has a negative eigenvalue; since Lemma 3.6 asserts positive definiteness everywhere on that open domain, a single such point -- or, equivalently, two non-representable triples whose convex combination is representable -- would falsify the geometric core of the proof.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.3: for an LLL instance satisfying $p2^d < 1$ in which every random variable affects at most three bad events, there is a sequential and local deterministic process that assigns values to all variables and avoids every bad event. Local means the choice for each variable depends only on the 1-hop neighborhood in the dependency graph, so the process can be parallelized: after a 2-hop coloring with $O(d^2)$ colors (computable in $\tilde{O}(d) + \log^* n$ rounds), iterating through the color classes gives an $O(d^2 + \log^* n)$-round deterministic LOCAL algorithm (Corollary 1.4). Together with known lower bounds for $p \geq 2^{-d}$, this makes $p = 2^{-d}$ a sharp threshold for variables affecting up to three events, the same spot as the rank-2 case, and is the paper's evidence for Conjecture 1.5 that the threshold is independent of $r$.

Load-bearing premise

The rank-3 result stands on the analytic claim that $f(a,b) = 4 + \frac{1}{2}(ab - 2a - 2b - \sqrt{ab(4-a)(4-b)})$ is convex on the triangle $a+b \le 4$; if that Hessian computation fails, the Variable Fixing Lemma and the threshold theorem lose their foundation.

Editorial extensions

If this is right

  • For rank-2 and rank-3 instances, $p < 2^{-d}$ admits deterministic distributed algorithms with $O(d + \log^* n)$ and $O(d^2 + \log^* n)$ rounds respectively, matching the $\Omega(\log^* n)$ lower bound on constant-degree graphs.
  • At $p = 2^{-d}$ and above, no algorithm can beat $\Omega(\log \log n)$ rounds (randomized) or $\Omega(\log n)$ rounds (deterministic), so the jump across the threshold is not an artifact of the algorithm.
  • The deterministic rank-3 algorithm improves on the previous best randomized algorithm for this regime, whose runtime was super-polylogarithmic.
  • The same fixing process yields deterministic algorithms for applications such as orientation in rank-3 hypergraphs and a weak splitting variant with 16 colors where every node sees at least 2 colors.
  • Almost all proof steps generalize to arbitrary $r$; only the convexity of the analogous surface is left open, which is the gap to Conjecture 1.5.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the threshold phenomenon holds for every $r$ as Conjecture 1.5 predicts, the distributed complexity of LLL would be governed by the exponential criterion alone; changing $r$ would only affect the polynomial dependence on $d$, not the $\log^* n$ term.
  • The geometric reduction suggests a testable route to the conjecture: for $r=4$ one could numerically search for pairs of non-representable tuples whose convex combination is representable; finding one would show where the framework breaks, and failing to find one would support the pattern.
  • Because the fixing order is adversarial and the bookkeeping is purely local, the construction acts as a deterministic derandomization of the resampling pipeline under a local probability bound; obtaining a similar result for criteria weaker than $p < 2^{-d}$ would probably require a different invariant.
  • The weak-splitting applications hint that the same technique could eventually attack the original weak splitting problem, whose efficient solution would imply efficient deterministic algorithms for maximal independent set and maximum-degree-plus-one vertex coloring.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies deterministic distributed algorithms for the Lovász Local Lemma under the exponential criterion p2^d < 1. It establishes a sharp threshold at p = 2^{-d}: for variables affecting at most two events it gives an O(d + log* n) deterministic LOCAL algorithm matching the known Ω(log* n) lower bound, and for variables affecting at most three events it gives an O(d^2 + log* n) deterministic algorithm under the same criterion. The rank-3 proof maintains an invariant P* on edge-endpoint labels of the dependency graph; the core technical step is showing that the set of representable probability-increase triples is incurved, which is reduced to an explicit characterization of that set and a convexity computation. The authors conjecture that the same threshold holds for any number r of events affected by a variable.

Significance. If the proof is completed, the result is significant: it gives the first sharp exponential threshold for deterministic distributed LLL and improves on prior randomized algorithms for rank-3 variables. The rank-2 argument is clean and self-contained, and the rank-3 framework—representable triples, incurvedness, and the evil-value contrapositive—is an elegant reduction of an algorithmic question to a two-variable analytic statement. The construction has no fitted parameters, and the lower-bound side relies on separate published results, so the claimed sharpness is grounded in external theorems rather than built into the algorithm.

major comments (3)
  1. [Appendix A, proof of Lemma 3.5] The displayed quadratic formula for the stationary points of c(x) is incorrect: for the equation x^2 - px + p = 0 the roots are (p ± sqrt(p^2 - 4p))/2, not p/2 ± sqrt(p^2 - 4p)/4. As printed, for the valid pair (a,b) = (1,2) the point called x1 lies outside the feasible interval [a/2, 2-b/2] = [1/2,1] and c(x1) does not equal f(1,2) = 2 - sqrt(3), so the proof as written does not identify the maximizing x. Since Lemma 3.5 is the characterization of S_rep used in Lemma 3.7 and hence in the Variable Fixing Lemma, this gap must be repaired; the subsequent algebra suggests that the intended root with the denominator 2 is correct, but the derivation and the case analysis for which root is feasible need to be rewritten.
  2. [Section 3, first paragraph] The reduction from rank-2 to rank-3 variables by adding a 'virtual third affected bad event' is not justified. If a new event is added for a rank-2 variable, it shares that variable with the two original events, so the new event must be a node adjacent to them in the dependency graph; doing this for many rank-2 variables can increase the maximum degree d of the original events, and the hypothesis p2^d < 1 does not survive the transformation. In addition, a virtual event whose probability does not depend on the variable would remain a real (possibly occurring) event at the end of the algorithm, so it cannot be treated as an ordinary bad event in the final probability argument. Please either supply a degree-preserving reduction or state and prove a direct variable-fixing lemma for rank-2 variables; the weighted version of the rank-2 argument mentioned in Section 3.1 would suffice.
  3. [Section 3.3, proof of Lemma 3.9] The identity sum_{i=1}^k p_i Inc(x,y_i) = 1 used in the proof of Lemma 3.9 is asserted for each affected event x, but it requires Pr[E_x | theta] > 0. The definition of Inc explicitly sets Inc(x,y) = 0 when this denominator is zero, and in that case the identity is false. The convex-combination construction of the triples s_i therefore collapses if any of the three events has conditional probability zero. This case is not excluded by P*, since P* only gives an upper bound on the conditional probability. Please handle zero-probability events separately (for example, by dropping the corresponding coordinate from the triple) or justify the identity by a limiting argument.
minor comments (5)
  1. [Lemma 3.5, statement] The set-builder notation '{(a,b,c) ⊆ R^3_{\ge 0} | ...}' should use the membership symbol '\in' instead of '\subseteq'.
  2. [Appendix A, proof of Lemma 3.5] In the case a,b ≠ 0, the claim that x2 is outside the feasible interval is only verified with the incorrect formula; after correcting the root formula, the two cases a > b and b > a must be handled explicitly, since the labeling of which root is feasible flips depending on the sign of a-b.
  3. [Section 1, Related Work and References] The reference [VG19] has garbled author names ('Vclav Rozho' should be 'Václav Rozhoň'); please fix the spelling and the title formatting.
  4. [Section 1, Techniques and Generalization] There is a typo 'assoiciated' in the discussion of the case r > 3; please correct it.
  5. [Figure 1] The caption refers to the 'orange shaded surface'; if the figure is printed in grayscale, the shading may be difficult to distinguish, so please add a pattern or explicit labeling.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the deterministic LLL upper bound is derived from an explicit invariant and convexity argument, and the sharp-threshold lower bounds are external published theorems.

full rationale

The paper's rank-3 result is self-contained in its constructive direction: it defines property P*, characterizes representable triples via Lemma 3.5, proves convexity of f in Lemma 3.6 by a Hessian computation, and derives the Variable Fixing Lemma from the incurredness of S_rep. None of these lemmas assumes the target theorem; the criterion p2^d<1 is used only at the end to turn the invariant into a probability bound. The threshold claim combines this upper bound with lower bounds from [BFH+16] and [CKP16]; although two current authors are among the authors of [BFH+16], that is a separately published lower-bound theorem for sinkless orientation, not a premise of the upper-bound proof, so it is independent support rather than a self-citation chain. The algorithm is not fitted to the output, and no parameter is renamed as a prediction. Any algebraic concern in the deferred proof of Lemma 3.5 would be a correctness issue, not circularity.

Assumptions & free parameters 0 free parameters · 6 assumptions · 1 invented entities

No free parameters: the threshold p < 2^{-d} is the assumed criterion, and the constants 2 and 4 in the bookkeeping scheme are structural choices, not fitted to data. The derivation is self-contained apart from standard probability, prior lower bounds used as external benchmarks, and standard LOCAL-model coloring subroutines. The only invented object is the virtual bad event, a harmless proof device.

assumptions (6)
  • standard math For any event E with positive conditional probability, Pr[E|theta] = sum_i p_i Pr[E|theta, X = y_i] (law of total probability).
    Used in Section 2 proof of Theorem 1.1 and Section 3.3 Lemma 3.9 to deduce that the weighted average of probability-increase factors equals 1.
  • domain assumption Randomized lower bound Omega(log log n) for LLL instances with p >= 2^{-d} in bounded-degree graphs [BFH+16].
    Invoked in the introduction and abstract to establish the sharpness of the threshold for randomized algorithms.
  • domain assumption Deterministic lower bound Omega(log n) for LLL instances with p >= 2^{-d} [CKP16].
    Invoked in the introduction and abstract to establish the sharpness of the threshold for deterministic algorithms.
  • domain assumption An O(d)-edge-coloring of a maximum-degree-d graph can be computed in O(d + log* n) LOCAL rounds [PR01].
    Used in Corollary 1.2 to schedule the rank-2 variable-fixing process.
  • domain assumption A 2-hop vertex-coloring with O(d^2) colors can be computed in O~(d + log* n) LOCAL rounds [FHK16].
    Used in Corollary 1.4 to schedule the rank-3 variable-fixing process.
  • standard math For C^2 functions, a positive semi-definite Hessian on an open convex domain implies convexity (Sylvester's criterion for definiteness) [BV04].
    Used in the proof of Lemma 3.6 in Appendix A to prove convexity of f(a,b).
invented entities (1)
  • Virtual third bad event attached to rank-2 variables
    purpose: Extends every rank-2 random variable to rank 3 in Section 3 so the rank-3 proof covers rank-2 variables uniformly; the dummy event's occurrence probability is defined to be unaffected by the variable's value.
    Purely a proof gadget; it has no empirical content or falsifiable consequence, and it does not appear in the lower-bound or application discussions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Sharp Threshold Phenomenon for the Distributed Complexity of the Lov\'asz Local Lemma." pith.science (2026). https://pith.science/paper/TEID3PFW

@misc{pith2026190806270,
  author       = {Pith},
  title        = {Pith review of: A Sharp Threshold Phenomenon for the Distributed Complexity of the Lov\'asz Local Lemma},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TEID3PFW}},
  note         = {Machine review of arXiv:1908.06270}
}
abstract

The Lov\'{a}sz Local Lemma (LLL) says that, given a set of bad events that depend on the values of some random variables and where each event happens with probability at most $p$ and depends on at most $d$ other events, there is an assignment of the variables that avoids all bad events if the LLL criterion $ep(d+1)<1$ is satisfied. In this paper, we study the dependency of the distributed complexity of the LLL problem on the chosen LLL criterion. We show that for the fundamental case of each random variable of the considered LLL instance being associated with an edge of the input graph, that is, each random variable influences at most two events, a sharp threshold phenomenon occurs at $p = 2^{-d}$: we provide a simple deterministic (!) algorithm that matches a known $\Omega(\log^* n)$ lower bound in bounded degree graphs, if $p < 2^{-d}$, whereas for $p \geq 2^{-d}$, a known $\Omega(\log \log n)$ randomized and a known $\Omega(\log n)$ deterministic lower bounds hold. In many applications variables affect more than two events; our main contribution is to extend our algorithm to the case where random variables influence at most three different bad events. We show that, surprisingly, the sharp threshold occurs at the exact same spot, providing evidence for our conjecture that this phenomenon always occurs at $p = 2^{-d}$, independent of the number $r$ of events that are affected by a variable. Almost all steps of the proof framework we provide for the case $r=3$ extend directly to the case of arbitrary $r$; consequently, our approach serves as a step towards characterizing the complexity of the LLL under different exponential criteria.

Figures

Figures reproduced from arXiv: 1908.06270 by the authors.

Figure 1
Figure 1. The set Srep of representable triples consists of all points in the first octant that are below the orange shaded surface. The reader might use the plot to convince himself of the fact that the set is incurved, that is, if two points s, s0 ∈ R 3 ≥0 are not in Srep then also the line connecting them does not intersect with the set Srep. Proof. In the proof of Theorem 1.1, we could essentially fix each random variable… view at source ↗
Figure 2
Figure 2. A quick calculation verifies that since a1 + b1 ≤ 2, a2 + c2 ≤ 2, and b3 + c3 ≤ 2, the illustrated triple (a, b, c) = 1 4 , 3 2 , 1 10  is representable. of the situation (resp. outcome) corresponding to subproperty (1) of property P ∗ : before fixing the variable in question, the values given by ϕ add up to at most 2 on each edge, hence the corresponding triple is representable, and Lemma 3.2 assures that the same… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Flows with minimal subdynamics

    math.DS 2025-09 conditional novelty 8.0 of 10

    Any countable family of infinite subsets of a countable group admits a free flow that is minimal along each subset, with applications to disjointness and Borel complete sections.

  2. Borel Local Lemma: arbitrary random variables and limited exponential growth

    math.CO 2024-12 conditional novelty 7.0 of 10

    A Borel LLL holds for arbitrary random variables when the dependency graph exponential growth rate is bounded by a constant s satisfying a slackened LLL condition.

Reference graph

Works this paper leans on

24 extracted references · 22 canonical work pages · cited by 2 Pith papers

  1. [1]

    A Parallel Algorithmic Version of the Local Lemma

    Noga Alon. A Parallel Algorithmic Version of the Local Lemma . Random Structures & Algorithms , 2(4):367--378, 1991

    work page 1991

  2. [2]

    An Algorithmic Approach to the Lov\' a sz Local Lemma

    J\' o zsef Beck. An Algorithmic Approach to the Lov\' a sz Local Lemma. Random Structures & Algorithms , 2(4):343--365, 1991

    work page 1991

  3. [3]

    A Lower Bound for the Distributed Lov\'asz Local Lemma

    Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempi\"ainen, Joel Rybicki, Jukka Suomela, and Jara Uitto. A Lower Bound for the Distributed Lov\'asz Local Lemma . In the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) , 2016

    work page 2016

  4. [4]

    On the complexity of distributed splitting problems

    Philipp Bamberger, Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, and Jara Uitto. On the complexity of distributed splitting problems. In the Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC) . ACM , 2019

    work page 2019

  5. [5]

    Convex Optimization

    Stephen Boyd and Lieven Vandenberghe. Convex Optimization . Cambridge University Press, 2004

    2004

  6. [6]

    An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model

    Yi - Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model . In the Proceedings of the Symposium on Foundations of Computer Science (FOCS) , pages 615--624, 2016

    work page 2016

  7. [7]

    A Time Hierarchy Theorem for the LOCAL Model

    Yi-Jun Chang and Seth Pettie. A Time Hierarchy Theorem for the LOCAL Model . In the Proceedings of the Symposium on Foundations of Computer Science (FOCS) , pages 156--167, 2017

    work page 2017

  8. [8]

    Distributed Algorithms for the Lov \'a sz Local Lemma and Graph Coloring

    Kai-Min Chung, Seth Pettie, and Hsin-Hao Su. Distributed Algorithms for the Lov \'a sz Local Lemma and Graph Coloring . Distributed Computing , 30(4):261--280, 2017

    work page 2017

Show all 24 references
  1. [9]

    Coloring Non-uniform Hypergraphs: A New Algorithmic Approach to the General Lov\' a sz Local Lemma

    Artur Czumaj and Christian Scheideler. Coloring Non-uniform Hypergraphs: A New Algorithmic Approach to the General Lov\' a sz Local Lemma . In the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 30--39, 2000

    2000

  2. [10]

    Problems and Results on 3-chromatic Hypergraphs and some Related Questions

    Paul Erd \"o s and L\' a szl \'o Lov \'a sz. Problems and Results on 3-chromatic Hypergraphs and some Related Questions . Colloquia Mathematica Societatis J \'a nos Bolyai , pages 609--627, 1974

    1974

  3. [11]

    Sublogarithmic Distributed Algorithms for Lov \'a sz Local Lemma, and the Complexity Hierarchy

    Manuela Fischer and Mohsen Ghaffari. Sublogarithmic Distributed Algorithms for Lov \'a sz Local Lemma, and the Complexity Hierarchy . In the Proceedings of the 31st International Symposium on Distributed Computing (DISC) , pages 18:1--18:16, 2017

    2017

  4. [12]

    Local Conflict Coloring

    Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski. Local Conflict Coloring . In the Proceedings of the Symposium on Foundations of Computer Science (FOCS) , pages 625--634, 2016

    2016

  5. [13]

    An Improved Distributed Algorithm for Maximal Independent Set

    Mohsen Ghaffari. An Improved Distributed Algorithm for Maximal Independent Set . In the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 270--277, 2016

    2016

  6. [14]

    Improved distributed degree splitting and edge coloring

    Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, and Jara Uitto. Improved distributed degree splitting and edge coloring. pages 19:1--19:15, 2017

    2017

  7. [15]

    Harris, and Fabian Kuhn

    Mohsen Ghaffari, David G. Harris, and Fabian Kuhn. On Derandomizing Local Distributed Algorithms . In the Proceedings of the Symposium on Foundations of Computer Science (FOCS) , pages 662--673, 2018

    2018

  8. [16]

    On the complexity of local distributed graph problems

    Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. On the complexity of local distributed graph problems. In the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 784--797. ACM , 2017

    2017

  9. [17]

    Distributed degree splitting, edge coloring, and orientations

    Mohsen Ghaffari and Hsin-Hao Su. Distributed degree splitting, edge coloring, and orientations. In Proc.\ 28th ACM-SIAM Symp.\ on Discrete Algorithms (SODA) , 2017

    2017

  10. [18]

    David G. Harris. Distributed approximation algorithms for maximum matching in graphs and hypergraphs. CoRR , abs/1807.07645, 2018

    2018 arXiv

  11. [19]

    Further Algorithmic Aspects of the Local Lemma

    Michael Molloy and Bruce Reed. Further Algorithmic Aspects of the Local Lemma . In the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 524--529, 1998

    1998

  12. [20]

    Moser and G\' a bor Tardos

    Robin A. Moser and G\' a bor Tardos. A Constructive Proof of the General Lov\' a sz Local Lemma . J. ACM , pages 11:1--11:15, 2010

    2010

  13. [21]

    Some Simple Distributed Algorithms for Sparse Networks

    Alessandro Panconesi and Romeo Rizzi. Some Simple Distributed Algorithms for Sparse Networks . Distributed Computing , 14(2):97--100, 2001

    2001

  14. [22]

    Conflict-free Colourings of Graphs and Hypergraphs

    J\' a nos Pach and G\' a bor Tardos. Conflict-free Colourings of Graphs and Hypergraphs . Combinatorics Probability and Computing , 18(5), 2009

    2009

  15. [23]

    Improved Algorithmic Versions of the Lov\' a sz Local Lemma

    Aravind Srinivasan. Improved Algorithmic Versions of the Lov\' a sz Local Lemma . In the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 611--620, 2008

    2008

  16. [24]

    Polylogarithmic-time deterministic network decomposition and distributed derandomization

    Václav Rozhoň and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. CoRR , abs/1907.10937, 2019

    1907 arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.