Pith. sign in

REVIEW 3 major objections 5 minor 22 references

Distributed weak independent sets in hypergraphs: Upper and lower bounds

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

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

Pith's one-line read This paper establishes LOCAL-round upper and lower bounds for weak maximal independent sets in hypergraphs, showing rank is an inherent lower-bound barrier while a gap-based relaxation admits zero-round randomized algorithms.

desk verdict Novel (α,β)-IS framework and a plausible k-weak MIS algorithm, but the advertised Ω(r) lower bound rests on a false matching argument and needs major repair. read the letter →

arxiv 2411.13377 v1 pith:PZQ3NGLL submitted 2024-11-20 cs.DC

Duncan Adamson , Will Rosenbaum , Paul G. Spirakis This is my paper · ORCID
classification cs.DC MSC 68W1505C6505C69
keywords distributedalgorithmsLOCALmodelhypergraphsweakmaximalindependentsetalpha-betaLovaszLemmarulingsetslowerbounds
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

The paper asks how many rounds of the LOCAL model a distributed network needs to elect an independent set when the network is a hypergraph, so one edge can span many vertices and a 'weak' independent set may take up to $k$ vertices from an edge. It proves that the weakest useful version, a 1-weak maximal independent set, cannot be found in $o(r)$ rounds on $r$-uniform hypergraphs of small degree, so the rank $r$ is an inherent barrier. On the algorithmic side, it gives a deterministic $k$-weak maximal independent set algorithm running in $O(\Delta^2(r-k)\log r + \Delta \log r \log^* r + \log^* n)$ rounds, and a family of $(\alpha,\beta)$-independent-set algorithms that run in $O(\Delta r/(\beta-\alpha+1)+\log^* n)$ rounds—or in zero rounds with high probability when the gap between $\beta$ and $\alpha$ is large. The $(\alpha,\beta)$ relaxation matters because it lets a network settle for a locally checkable approximation of maximality, which can be dramatically cheaper than true maximality.

What carries the argument

The carrying object is the $(\alpha,\beta)$-independent set relaxation together with two accounting mechanisms. For the upper bounds, the algorithms split every edge into small parts, color the underlying graph of the split hypergraph, and activate color classes one by one; the saturation of an edge—the number of its vertices already in the set—and its phase control how many active vertices may still be added, so the $k$-weak MIS algorithm doubles the saturation of some incident edge in each phase and charges the $\log r$ phases against $\Delta$ incident edges. For the lower bounds, the key mechanism is reduction: a 1-weak MIS solver is invoked repeatedly, deleting matched hyperedges, to build a maximal matching whose $\Omega(r\Delta)$ lower bound transfers to $\Omega(r)$; and blow-up constructions replace each graph vertex by $r/2$ (or $k$) copies, so that a 1-weak or $k$-weak MIS in the hypergraph projects back to an MIS in the original graph, transferring the graph $\Omega(\Delta+\log^* n)$ bound. A third mechanism is a Lovász Local Lemma formulation—encoding the desired set as an outcome avoiding a family of bad events—with independent Bernoulli choices whose mean per edge is $(\alpha+\beta)/2$ and a Chernoff bound giving the required gap condition, plus a constructive LLL algorithm converting existence into a deterministic $O(\log^2 n)$-round algorithm.

What would settle it

Run a candidate deterministic 1-weak MIS algorithm on the family of $r$-uniform hypergraphs with $r\Delta\log(r\Delta)=O(\log n)$; a single instance that terminates in $o(r)$ rounds refutes Theorem 7. To test the proof reduction itself, feed an algorithm known to work only on $r$-uniform inputs to the sequence $G_0,G_1,\ldots$ generated by deleting vertices and edges; if the algorithm's output on some non-uniform $G_i$ is not a 1-weak MIS, the reduction's invocation of the algorithm on $G_{i-1}$ is invalid.

Watch

Extended reading notes

Core claim

The central claim is a complexity map for hypergraph independent sets. For $r$-uniform hypergraphs of maximum degree $\Delta$, a $k$-weak maximal independent set—a set in which every edge has at most $k$ selected vertices and every unselected vertex sits in an edge with $k$ selected vertices—can be found in $O(\Delta^2(r-k)\log r + \Delta \log r \log^* r + \log^* n)$ LOCAL rounds. In the opposite direction, every deterministic 1-weak MIS algorithm needs $\Omega(r)$ rounds on the family $r\Delta\log(r\Delta)=O(\log n)$, and $\Omega(\Delta+\log^* n)$ rounds on even-rank hypergraphs; for odd $k$, a $k$-weak MIS on $2k$-uniform hypergraphs also needs $\Omega(\Delta+\log^* n)$. The paper further introduces $(\alpha,\beta)$-independent sets, where the set is $\beta$-weak and every vertex sits in an edge containing at least $\alpha$ selected vertices, and shows these can be found deterministically in $O(\Delta r/(\beta-\alpha+1)+\log^* n)$ rounds, and with zero rounds of communication with high probability when $(\beta-\alpha)^2/(\beta+\alpha)\ge 6c\log n+6$.

Load-bearing premise

The $\Omega(r)$ lower bound assumes that the 1-weak MIS algorithm being ruled out can be applied to each smaller subhypergraph created by deleting vertices and edges, even though those subhypergraphs are no longer $r$-uniform and the family condition $r\Delta\log(r\Delta)=O(\log n)$ is not re-checked after $n$ shrinks.

Editorial extensions

If this is right

  • For $k$ close to $r$ and small $\Delta$, the $O(\Delta^2(r-k)\log r + \Delta\log r\log^* r + \log^* n)$ algorithm beats the trivial $O(r\Delta+\log^* n)$ coloring method, so weak maximal independent sets become cheap at high weakness.
  • When the gap $\beta-\alpha$ is large enough that $(\beta-\alpha)^2/(\beta+\alpha)\ge 6c\log n+6$, an $(\alpha,\beta)$-independent set can be produced with zero communication, meaning the selected set is correct with high probability from purely local random choices.
  • The deterministic $(\alpha,\beta)$-IS algorithm yields $(2,k)$-ruling sets in $O(\Delta(k + (2^{k-1}/3^{k-1})r)+\log^* n)$ rounds, extending ruling-set constructions from graphs to hypergraphs.
  • The $\Omega(r)$ lower bound for 1-weak MIS shows that for the weakest nontrivial requirement, no algorithm can escape a linear dependence on rank even when the degree is tiny.
  • For $k<k'$, the observation that a $k$-weak MIS extends to a $k'$-weak MIS suggests a monotone difficulty scale, with the paper's evidence pointing to smaller $k$ being harder.

Reading between the lines

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

  • A natural test of the algorithm's mechanism is to run the phase-doubling procedure on non-uniform hypergraphs, replacing $r$ by the maximum edge size; the saturation accounting is edge-local, so the proof structure should survive even if the round bound changes.
  • The zero-round threshold has the flavor of a phase transition: once the gap condition depends on $n$ rather than on $r\Delta$, communication stops buying anything. Stretching the constant 6 down to the LLL threshold $ep(d+1)\le 1$ would be the clean way to test how sharp that transition is.
  • For an application that only needs approximate maximality, the zero-round $(\alpha,\beta)$-IS is a ready-made primitive: when $(\beta-\alpha)^2/(\beta+\alpha)\ge 6c\log n+6$, each vertex decides independently and the network avoids all coordination cost.
  • The remaining gap for 1-weak MIS—an $O(r\Delta+\log^* n)$ upper bound against an $\Omega(\Delta+r+\log^* n)$ lower bound—suggests the true complexity may be closer to $r\Delta$; matching reductions alone likely cannot close it.
Share X Bluesky LinkedIn Reddit HN

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 distributed algorithms for weak independent sets in hypergraphs in the LOCAL model. It introduces (α,β)-independent sets, gives an LLL-based existence/algorithmic formulation, a zero-round randomized construction, deterministic algorithms for (α,β)-IS and k-weak MIS, and three lower-bound theorems for 1-weak and k-weak MIS. The headline upper bound, Theorem 23, is a O(∆²(r−k) log r + ∆ log r log* r + log* n)-round deterministic algorithm for k-weak MIS, generalizing a result of Balliu et al. The headline lower bounds are Ω(r) (Theorem 7) and Ω(∆+log* n) (Theorems 9 and 10) for specific families of hypergraphs.

Significance. If correct, the upper bounds would be a meaningful step beyond the r−1-weak MIS algorithm of Balliu et al., and the (α,β)-IS framework is a natural generalization worth studying. The LLL formulation in Lemma 12 is a clean reduction, and Theorems 19 and 23 propose concrete algorithmic ideas with explicit round counts. The paper is not hiding fitted parameters: the main theorems are stated as explicit functions of ∆, r, n, and the proofs invoke standard external results (LLL, coloring, matching lower bounds). However, the advertised lower-bound result of Theorem 7 rests on an invalid construction, and the zero-round high-probability claim in Corollary 14 is not justified for the stated parameter range. These issues affect two of the paper's headline contributions, so the paper needs substantial revision before its claims can be relied upon.

major comments (3)
  1. [Theorem 7, proof steps 2 and 3] The claim that each M_i is a matching is false. For two vertices v,u in the 1-weak MIS S_i, the arbitrarily chosen incident hyperedges e_v and e_u may intersect in a vertex outside S_i. Example with r=3: e1={v1,w,x1}, e2={v2,w,x2}, and S={v1,v2} is a 1-weak MIS, but no choice of one incident edge per S-vertex yields a matching because both edges necessarily contain w. Therefore the subsequent assertions that M = ∪ M_i is a matching and that M is a maximal matching to which Theorem 8 applies are unsupported. The reduction to maximal matching collapses, so Theorem 7's Ω(r) lower bound is not established by the presented argument. The proof also does not verify that each G_{i-1} still satisfies the family condition r∆ log(r∆)=O(log n) after vertices are deleted, but the matching defect is already decisive.
  2. [Corollary 14, Eq. (4)] The zero-round high-probability claim is not justified by the stated condition. To conclude that the sampled set is an (α,β)-IS with probability 1−1/n^c one must union-bound over all n vertex events and all edge events. The per-event Chernoff bound in Eq. (3) gives a failure probability of at most 2 exp(−(β−α)²/(6(β+α))). With condition (4), this is at most 2/(e n^c), but the number of edges can be as large as n∆. The union bound then gives failure probability roughly (2/e) n^{1−c} ∆, which can exceed n^{−c} whenever ∆ is large (e.g., ∆=n). The condition omits ∆ (or the number of edges), which is why the proof fails. A corrected statement would need a bound such as (β−α)²/(β+α) ≥ 6c log n + 6 log ∆ + O(1), or an explicit bound on m in terms of n, ∆, and r.
  3. [Lemma 17 and Section 5] The statement of Lemma 17 is not well-formed: 'produces an m-weak independent set with expected size of m at least r/2k' mixes the weakness parameter m with the size of the produced set. As written it is not a theorem about the produced vertex set. Moreover, the analysis does not establish any k-weak independence guarantee: the procedure deletes one randomly chosen vertex per edge, but the surviving vertices in a given hyperedge can still be numerous. The argument that each part u_{e,i} retains at least one vertex gives only a lower bound on the intersection size per edge, not an upper bound of the form required for a k-weak (or m-weak) independent set. This section's claimed contribution ('0-round algorithm producing an m-weak independent set') is therefore not supported by the presented proof.
minor comments (5)
  1. [Theorem 9, proof] The reduction from a graph G on N vertices constructs a hypergraph G' on n = N·r/2 vertices. The Ω(∆+log* n) graph lower bound then transfers to Ω(∆+log* N) = Ω(∆+log*(2n/r)), not automatically Ω(∆+log* n) when r is close to n. The proof does not address this change in the vertex count; the theorem as stated requires additional argument or a restriction on r.
  2. [Theorem 23, proof, inequality (5)] The proof states that inequality (5) is 'clearly true when |Vc|=1' (the case where A_e is kept as a single part). This is not correct: if A_e is a single part and has size larger than 1, proper coloring of H' gives |Vc∩e|=1, but the right-hand side ½(k−sat(e)) can be smaller than 1 (e.g. k−sat(e)=1). The argument can be repaired by using the algorithm's actual add condition |Vc∩e| ≤ k−sat(e), which holds because k−sat(e)≥1 for active, unsaturated edges, but the proof as written needs this correction.
  3. [Algorithm 4, line 6] The instruction 'partition A_e into ⌊|A_e|/4⌋ parts of size at most 5' is not a well-defined partition (for example, |A_e|=6 would require two parts but ⌊6/4⌋=1). This is likely a typo for a partition into ⌈|A_e|/5⌉ parts or into parts of size at most 4; the proof's bound |Vc∩e| ≤ ¼|A_e| should be aligned with the actual part size.
  4. [Section 6.1 and Theorem 19 proof] There are small inconsistencies: the proof of Theorem 19 says 'O(∆r/α + log* n)' while the theorem and surrounding text use δ=β−α+1; the 'α-defective coloring' phrase should read 'δ-defective coloring'; and the claim that 'G′ is a regular graph' is not justified — it is only an arbitrary graph with bounded degree.
  5. [Conclusion] The conclusion states 'our lower bound Ω(∆+r+log* n)' for 1-weak MIS, but the paper only proves Ω(r) (Theorem 7, currently invalid) and Ω(∆+log* n) (Theorems 9–10) as separate bounds, not a single combined bound. The sentence should be rephrased to match the actual theorems.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: upper bounds use external LLL/coloring machinery and lower bounds import external matching/MIS bounds; no fitted parameter is presented as a prediction.

full rationale

The paper's claimed derivations are not circular. The upper-bound results (Lemma 12, Corollaries 13-14, Theorems 19 and 23, and the ruling-set corollaries) are self-contained reductions to standard external machinery: the Lovász Local Lemma, Chernoff bounds, Linial's coloring, and the Maus-Tonoyan coloring algorithm. No parameter is fitted to the target quantity and then renamed as a prediction; in particular, the zero-round randomized construction is an explicit probabilistic existence assertion with stated concentration bounds, not a fitted input. The lower bounds (Theorems 7, 9, 10) reduce from external lower bounds of Balliu et al. [2,3]; the proof of Theorem 7 appears defective because the selected hyperedges are not shown to form a matching, but that is a correctness gap, not a circularity: the reduction invokes an external Ω(rΔ) matching lower bound and does not define its conclusion into its hypothesis. There is no load-bearing self-citation: the authors cite prior general algorithms and lower bounds, not their own prior assertions, and the one self-referential remark ('we believe our definition of (α,β)-independent set is novel') is not used as an argument. Consequently, the derivation chain is independent of its conclusions, and the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The central claims rest on standard concentration theorems and on imported distributed algorithms and lower bounds from the cited literature. No data-fitting parameters exist. The unresolved assumptions are not axioms in the mathematical sense but family-closure properties of the lower-bound reductions, flagged separately in red_flags.

assumptions (7)
  • standard math Lovász Local Lemma and its constructive Moser-Tardos version (cited [10,21])
    Used in Section 4 to show existence and distributed construction of (alpha, beta)-IS under condition (1); the paper relies on the theorem rather than proving it.
  • standard math Chernoff bound for sums of independent 0-1 random variables (cited [20])
    Used in Lemma 12 and Corollary 14 to bound the probability that an edge's sum deviates from its mean.
  • domain assumption Balliu et al. maximal matching lower bound Omega(r Delta) in r-uniform hypergraphs (Theorem 8, [3])
    Basis for Theorem 7's Omega(r) lower bound via reduction; the paper imports this external result and its family conditions.
  • domain assumption Balliu et al. Omega(Delta + log* n) MIS lower bound on regular graphs (cited [2])
    Used as the source lower bound in Theorems 9 and 10 through hypergraph constructions.
  • domain assumption Maus-Tonoyan local conflict coloring algorithm with O(sqrt(Delta) log Delta + log* n) rounds (cited [19])
    Used for the delta-defective coloring in Section 6.1 and for coloring H' in Section 6.2; runtime and correctness are imported.
  • domain assumption Linial's O(log* n)-round (Delta+1)-coloring algorithm (cited [17])
    Used in Theorem 23 to provide the initial proper coloring of the underlying graph.
  • domain assumption Ghaffari-Grunau deterministic network decomposition (cited [12])
    Used in Lemma 5 to derive the O(log^2 n) deterministic k-weak MIS algorithm via centralization within components.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Distributed weak independent sets in hypergraphs: Upper and lower bounds." pith.science (2026). https://pith.science/paper/PZQ3NGLL

@misc{pith2026241113377,
  author       = {Pith},
  title        = {Pith review of: Distributed weak independent sets in hypergraphs: Upper and lower bounds},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PZQ3NGLL}},
  note         = {Machine review of arXiv:2411.13377}
}
read the original abstract

In this paper, we consider the problem of finding weak independent sets in a distributed network represented by a hypergraph. In this setting, each edge contains a set of r vertices rather than simply a pair, as in a standard graph. A k-weak independent set in a hypergraph is a set where no edge contains more than k vertices in the independent set. We focus two variations of this problem. First, we study the problem of finding k-weak maximal independent sets, k-weak independent sets where each vertex belongs to at least one edge with k vertices in the independent set. Second we introduce a weaker variant that we call (\alpha, \beta)-independent sets where the independent set is \beta-weak, and each vertex belongs to at least one edge with at least \alpha vertices in the independent set. Finally, we consider the problem of finding a (2, k)-ruling set on hypergraphs, i.e. independent sets where no vertex is a distance of more than k from the nearest member of the set. Given a hypergraph H of rank r and maximum degree \Delta, we provide a LLL formulation for finding an (\alpha, \beta)-independent set when (\beta - \alpha)^2 / (\beta + \alpha) \geq 6 \log(16 r \Delta), an O(\Delta r / (\beta - \alpha + 1) + \log^* n) round deterministic algorithm finding an (\alpha, \beta)-independent set, and a O(\Delta^2(r - k) \log r + \Delta \log r \log^* r + \log^* n) round algorithm for finding a k-weak maximal independent set. Additionally, we provide zero round randomized algorithms for finding (\alpha, \beta) independent sets, when (\beta - \alpha)^2 / (\beta + \alpha) \geq 6 c \log n + 6 for some constant c, and finding an m-weak independent set for some m \geq r / 2k where k is a given parameter. Finally, we provide lower bounds of \Omega(\Delta + \log^* n) and \Omega(r + \log^* n) on the problems of finding a k-weak maximal independent sets for some values of k.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 17 canonical work pages

  1. [1]

    Network decomposition and locality in distributed computation

    Baruch Awerbuch, Andrew V Goldberg, Michael Luby, and Serge A Plotkin. Network decomposition and locality in distributed computation. In FOCS , volume 30, pages 364--369. Citeseer, 1989

    work page 1989

  2. [2]

    Lower bounds for maximal matchings and maximal independent sets

    Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mika \"e l Rabie, and Jukka Suomela. Lower bounds for maximal matchings and maximal independent sets. Journal of the ACM (JACM) , 68(5):1--30, 2021

    work page 2021

  3. [3]

    Distributed Maximal Matching and Maximal Independent Set on Hypergraphs , pages 2632--2676

    Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. Distributed Maximal Matching and Maximal Independent Set on Hypergraphs , pages 2632--2676. URL: https://epubs.siam.org/doi/abs/10.1137/1.9781611977554.ch100, https://arxiv.org/abs/https://epubs.siam.org/doi/pdf/10.1137/1.9781611977554.ch100 arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9...

    doi:10.1137/1.9781611977554.ch100

  4. [4]

    Improved distributed lower bounds for mis and bounded (out-) degree dominating sets in trees

    Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. Improved distributed lower bounds for mis and bounded (out-) degree dominating sets in trees. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing , pages 283--293, 2021

    work page 2021

  5. [5]

    Distributed lower bounds for ruling sets

    Alkida Balliu, Sebastian Brandt, and Dennis Olivetti. Distributed lower bounds for ruling sets. SIAM Journal on Computing , 51(1):70--115, 2022

    work page 2022

  6. [6]

    Distributed ( + 1)-coloring in linear (in ) time

    Leonid Barenboim and Michael Elkin. Distributed ( + 1)-coloring in linear (in ) time. In Proceedings of the forty-first annual ACM symposium on Theory of computing , pages 111--120, 2009

    work page 2009

  7. [7]

    The locality of distributed symmetry breaking

    Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. Journal of the ACM (JACM) , 63(3):1--45, 2016

    work page 2016

  8. [8]

    An automatic speedup theorem for distributed problems

    Sebastian Brandt. An automatic speedup theorem for distributed problems. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing , pages 379--388, 2019

    work page 2019

Show all 22 references
  1. [9]

    A lower bound for the distributed lov \'a sz local lemma

    Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempi \"a inen, Joel Rybicki, Jukka Suomela, and Jara Uitto. A lower bound for the distributed lov \'a sz local lemma. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pages 479...

    2016

  2. [10]

    Problems and results on 3-chromatic hypergraphs and some related questions

    Paul Erdos and L \'a szl \'o Lov \'a sz. Problems and results on 3-chromatic hypergraphs and some related questions. Infinite and finite sets , 10(2):609--627, 1975

    1975

  3. [11]

    An improved distributed algorithm for maximal independent set

    Mohsen Ghaffari. An improved distributed algorithm for maximal independent set. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms , pages 270--277. SIAM, 2016

    2016

  4. [12]

    Near-optimal deterministic network decomposition and ruling set, and improved mis, 2024

    Mohsen Ghaffari and Christoph Grunau. Near-optimal deterministic network decomposition and ruling set, and improved mis, 2024. URL: https://arxiv.org/abs/2410.19516, https://arxiv.org/abs/2410.19516 arXiv:2410.19516

    2024 arXiv

  5. [13]

    Improved deterministic network decomposition

    Mohsen Ghaffari, Christoph Grunau, and V \'a clav Rozho n . Improved deterministic network decomposition. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2904--2923. SIAM, 2021

    2021

  6. [14]

    Efficient distributed computation of mis and generalized mis in linear hypergraphs

    Fabian Kuhn and Chaodong Zheng. Efficient distributed computation of mis and generalized mis in linear hypergraphs. arXiv preprint arXiv:1805.03357 , 2018

    2018 arXiv

  7. [15]

    Distributed symmetry breaking in hypergraphs

    Shay Kutten, Danupon Nanongkai, Gopal Pandurangan, and Peter Robinson. Distributed symmetry breaking in hypergraphs. In Distributed Computing: 28th International Symposium, DISC 2014, Austin, TX, USA, October 12-15, 2014. Proceedings 28 , pages 469--483. Springer, 2014

    2014

  8. [16]

    Distributive graph algorithms global solutions from local data

    Nathan Linial. Distributive graph algorithms global solutions from local data. In 28th Annual Symposium on Foundations of Computer Science (sfcs 1987) , pages 331--335. IEEE, 1987

    1987

  9. [17]

    Locality in distributed graph algorithms

    Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on computing , 21(1):193--201, 1992

    1992

  10. [18]

    Distributed graph coloring made easy

    Yannic Maus. Distributed graph coloring made easy. ACM Transactions on Parallel Computing , 10(4):1–21, December 2023. URL: http://dx.doi.org/10.1145/3605896, https://doi.org/10.1145/3605896 doi:10.1145/3605896

    2023 doi

  11. [19]

    Local conflict coloring revisited: Linial for lists

    Yannic Maus and Tigran Tonoyan. Local conflict coloring revisited: Linial for lists. arXiv preprint arXiv:2007.15251 , 2020

    2007 arXiv

  12. [20]

    Chernoff Bounds , page 61–89

    Michael Mitzenmacher and Eli Upfal. Chernoff Bounds , page 61–89. Cambridge University Press, 2005

    2005

  13. [21]

    Moser and Gábor Tardos

    Robin A. Moser and Gábor Tardos. A constructive proof of the general lovász local lemma. Journal of the ACM , 57(2):1–15, January 2010. URL: http://dx.doi.org/10.1145/1667053.1667060, https://doi.org/10.1145/1667053.1667060 doi:10.1145/1667053.1667060

    2010

  14. [22]

    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

Pith tools

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