Truly Work-efficient Parallel Deterministic $(\Delta+1)$-coloring and Maximal Independent Set

Adam Melrod; Chase Hutton

REVIEW 2 major objections 5 minor 41 references

Truly Work-efficient Parallel Deterministic $(\Delta+1)$-coloring and Maximal Independent Set

T0 review · 2 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 Deterministic parallel algorithms for MIS and $(\deg+1)$-coloring run in $O(n+m)$ work and polylogarithmic depth, matching the sequential greedy bound.

desk verdict Strong paper with a solid MIS result and an elegant core, but the coloring theorem hinges on an unproved list-coloring adaptation of Luby's algorithm that must be supplied. read the letter →

arxiv 2608.08296 v1 pith:PL3VDPG3 submitted 2026-08-08 cs.DS cs.DC

Chase Hutton , Adam Melrod This is my paper · ORCID

classification cs.DScs.DC

keywords parallelalgorithmswork-depthmodelmaximalindependentsetgraphcoloringderandomizationpairwiseindependencesparsepartitiondeterministic

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 settle a three-decade-old question: whether the two classic symmetry-breaking problems, maximal independent set and $(\deg+1)$-coloring, can be solved deterministically in parallel with work matching the sequential greedy bound $O(n+m)$, while keeping depth polylogarithmic. The authors claim yes for both, giving the first work-efficient deterministic parallel algorithms for either problem. If the claim is right, the previous best deterministic coloring bound drops by a $\log^2 n$ factor and the last $\mathrm{poly}(\log\log n)$ overhead in MIS disappears. The route is a bootstrapping scheme: first partition the graph into polylogarithmically many pieces with very few internal edges, solve each piece by an existing polylog-overhead deterministic subroutine, and charge the extension steps to edges once each.

What carries the argument

The central object is the ordered $L$-sparse partition of Theorem 4.2, built by recursive bisection whose internal edge count decays by a factor $5/12$ at every level. The bisection step is derandomized through the bit-pair benefit problem: with vertices paired by an involution that maps consecutive degrees to each other, the number of cut edges is written as $B(x)=\sum_{\{u,v\}\in P}\Psi_{uv}(x_u \oplus x_v)$, and a good assignment is found by drawing bits from the pairwise-independent space $x_u(r)=\bigoplus_t u_t r_t$ and fixing the seed coordinates $r_t$ one at a time. Grouping constraints by the most significant set bit of $u\oplus v$ makes each constraint contribute exactly once, which is what keeps the work linear. The involution guarantees the two sides' internal edge counts differ by at most $\Delta/2$, and the derandomized cut of at least $m/2$ edges forces each side to have at most $5m/12$ edges; iterating this partition and applying Theorem 5.1 yields the final linear-work algorithms.

What would settle it

Run two checks: implement the Theorem 4.2 partition and verify the $5m/12$ edge-decay on random and worst-case graphs; and run the coloring subroutine on random residual palettes to see if any edge is monochromatic. A violation of either check would refute the corresponding half of the paper's claim.

Watch

Extended reading notes

Core claim

The paper's central claim is that both problems admit deterministic parallel algorithms with work $O(n+m)$ and depth $\mathrm{poly}(\log n)$, matching the sequential greedy bound (Theorems 1.1 and 1.2). For coloring this improves the previous best deterministic work bound by a factor of $\log^2 n$; for MIS it removes the final $\mathrm{poly}(\log\log n)$ overhead from the previous best. The argument shows that both problems are extendable: a partial solution determines a residual instance on the unprocessed vertices, at the cost of inspecting each edge joining the processed part to the unprocessed part exactly once. The authors prove a bootstrapping theorem (Theorem 5.1) that upgrades any deterministic algorithm with polylogarithmic work overhead for such a problem to a fully work-efficient one, provided the graph can be partitioned into sparse pieces as in Theorem 4.2. For coloring, the residual pieces are list-coloring instances, and the paper invokes the deterministic coloring subroutine from [Lub93], assuming it works with arbitrary sorted palettes of size $\deg(v)+1$.

Load-bearing premise

The coloring theorem rests on the unproved assertion, stated in the last paragraph of Corollary 5.3, that the deterministic coloring subroutine remains correct when each vertex is given an arbitrary sorted palette of size $\deg(v)+1$ rather than the uniform palette $\{1,\dots,\Delta+1\}$; if that adaptation fails, Corollary 5.3 loses its subroutine.

Editorial extensions

If this is right

With the existing work-efficient deterministic maximal matching algorithms, all three classical symmetry-breaking problems — MIS, maximal matching, and $(\deg+1)$-coloring — now have deterministic parallel algorithms with $O(n+m)$ work and polylogarithmic depth.
The coloring work bound drops from $O((n+m)\log^2 n)$ to $O(n+m)$, and the MIS work bound drops from $(n+m)\,\mathrm{poly}(\log\log n)$ to $O(n+m)$.
On a $p$-processor shared-memory machine, either algorithm runs in $O((n+m)/p + \mathrm{poly}(\log n))$ time deterministically, so the trivial sequential greedy cost is matched once parallelism increases.
Any future deterministic subroutine for an extendable graph problem that runs in polylog work overhead can be plugged into Theorem 5.1 and automatically upgraded to linear work.

Reading between the lines

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

The sparse-partition scheme is stated for MIS and coloring, but nothing in Theorem 5.1 is specific to them; maximal matching is the natural next target, and the linear-work bit-pair technique was originally developed for it.
The coloring theorem's dependence on the unproved palette adaptation of the subroutine means the result is only as strong as that assumption; if the adaptation fails, the same partition and bootstrapping would still work with any other poly-log-overhead deterministic list-coloring algorithm.
Because the MIS algorithm never needs concurrent writes, it suggests work-efficient deterministic MIS is achievable on a CREW PRAM, whereas the coloring extension step needs only common-value writes.
The constants in the partition (the $5/12$ edge-decay factor and the $O(k^{4})$ number of pieces) are explicit enough that a direct implementation on small graphs could verify the claimed sparsity before any large-scale deployment.

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.

Desk Editor's Note

read the letter

Short version: this is a genuinely interesting paper and, for MIS, I believe the argument is sound. The coloring theorem, however, depends on an unproved assertion about Luby's deterministic coloring algorithm, and that needs to be pinned down before I'd trust Theorem 1.2.

What's new: the deterministic linear-work solution to the bit-pair benefit problem in Han's style (Section 3) is carefully done; the involution-based partition lemma that forces an edge cut of size at least m/2 is elegant; and the bootstrapping theorem (Theorem 5.1) is a nice abstraction. If the pieces hold, these complete the picture for the three classical symmetry-breaking problems. The MIS corollary uses only standard MIS subroutines, and I could not find a flaw in its proof. The proof of Theorem 5.1 is slightly loose about newly isolated vertices in the MIS case, but that does not break the work bound.

The real problem is Corollary 5.3. The final paragraph asserts that Luby's coloring algorithm works for arbitrary sorted palettes of size deg(v)+1, with no proof or pointer to a theorem in [Lub93]. This is not cosmetic: the residual instances after the extension step are list instances with palettes of varying sizes, while the standard Luby algorithm is presented for the uniform palette {1,...,Δ+1}. Whether it can be derandomized to handle vertex-specific lists is exactly the kind of thing that needs a proof. If it is false, Theorem 1.2 collapses, though the MIS result still stands.

Minor issues: the recursion in Theorem 4.2 has some implementation details sketched (dummy vertex, self-pair edges, duplicate adjacency entries), but those look resolvable. The proof of Theorem 5.1 relies on the partition's isolated list to cover all isolated vertices in T_i, which is slightly inaccurate for MIS as noted; again not fatal.

Who should read this: anyone working on parallel symmetry-breaking or derandomization. If the coloring gap is closed, it is a significant result. As is, it deserves a serious referee, not a desk reject, because the core machinery is novel and the MIS result alone is worth publishing. I would tell the authors to add a rigorous proof of the list-coloring claim (or restructure the coloring argument to avoid it) before acceptance.

Referee Report

2 major / 5 minor

Summary. The paper claims deterministic parallel algorithms for maximal independent set and (deg+1)-coloring that run in O(n+m) work and polylogarithmic depth. The technical core is a new linear-work deterministic solution to Luby's bit-pair benefit problem (Theorem 3.1), an involution-based edge-balanced vertex partition (Theorem 4.2), and a bootstrapping theorem (Theorem 5.1) that upgrades any deterministic algorithm with polylogarithmic work overhead into a work-efficient one for any 'extendable' problem. The MIS corollary is supported by known deterministic MIS algorithms, while the coloring corollary depends on an asserted but unproved adaptation of Luby's deterministic coloring algorithm to list-coloring instances with arbitrary sorted palettes of size deg(v)+1.

Significance. If both theorems are correct, this resolves a long-standing open question in parallel algorithms: it would be the first work-efficient deterministic parallel algorithm for MIS, removing the final poly(log log n) overhead of [GG25], and the first for (Δ+1)-coloring, improving the best previous work bound by a factor of log^2 n. The paper's own contributions—the bit-pair benefit algorithm of Section 3, the involution-based balancing lemma of Section 4, and the clean bootstrapping framework of Section 5—are interesting and appear correct. The MIS result is well supported. However, the coloring theorem is not fully established as submitted: its residual list-coloring subroutine is asserted without proof, and the palette-update step makes a range assumption that is inconsistent with the stated generality of arbitrary palettes. These are load-bearing gaps for Theorem 1.2, though they appear fixable.

major comments (2)

[Corollary 5.3, final paragraph] The assertion that "Luby's coloring algorithm is presented as only using Δ+1 colors, but his exact algorithm works given that each vertex v has a sorted palette C(v) of size deg(v)+1" is unproved and is load-bearing for Theorem 1.2. Theorem 5.1's hypothesis (B) requires a deterministic subroutine for the residual list-coloring instances that arise on the pieces of the partition; those instances are not ordinary (Δ+1)-coloring instances because colors used by earlier neighbors have been removed from the palettes. Please supply a proof of this adaptation, or a precise citation to a lemma in [Lub93] that establishes both correctness and the stated O((n'+m') log^a n) work bound for arbitrary sorted palettes. Without this, Corollary 5.3 does not provide a subroutine to plug into Theorem 5.1.
[Corollary 5.3, palette update] The residual palette computation uses a Boolean array indexed by {1,...,deg_G(v)+1} and skips neighbor colors φ(u)>deg_G(v)+1, justified by the claim that "colors above deg_G(v)+1 never lie in C(v)". This claim is false when C(v) is an arbitrary sorted palette of size deg_G(v)+1; for example, with deg_G(v)=2 and C(v)={10,20,30}, a neighbor may already use color 20, which belongs to C(v) but is not marked by the Boolean array. If the intended theorem is only for palettes of the form {1,...,deg_G(v)+1}, that restriction should be stated in Theorem 1.2; if arbitrary palettes are intended, the update step must instead mark neighbor colors via a dictionary or a merge with the sorted palette, at the same asymptotic work.

minor comments (5)

[Section 1, paragraph on [GG25]] Typo: "amound" should be "amount".
[Section 5, before Theorem 5.1] Typo: "Luby's algortihm" should be "Luby's algorithm".
[Corollary 5.3, truncation sentence] The notation deg(v) changes meaning in the sentence "Each palette C'(v) is then truncated to size deg(v)+1": earlier deg(v) means deg_G(v), while here it must mean the degree in G[W]. Please clarify the notation.
[Lemma 4.1, benefit instance construction] The phrase "parallel constraints arising from distinct edges" is unclear; since P is allowed to be a multiset, it would be clearer to say that distinct edges may give rise to multiple constraints on the same pair of variables.
[Theorem 4.2, statement] The statement says the partition is a "(poly k)-partition"; the proof shows the number of parts is O(k^4), so this precise bound should be stated in the theorem.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the linear-work bootstrapping argument is self-contained, and the only soft spot is an unproved external-subroutine claim in Corollary 5.3, which is a correctness concern rather than circular reasoning.

full rationale

The derivation chain is not circular. Theorem 5.1 is a bootstrapping theorem: it upgrades a subroutine with O((n'+m') log^a n) work on sparse pieces to O(n+m) total work. The MIS corollary obtains its subroutine from external algorithms [Lub93; GS89b; Han96], and the sparse partition is supported by a fully worked-out proof of the bit-pair benefit problem in Section 3, including implementation details in Section 3.3. No parameter is fitted to the claimed output, no prediction is renamed input, and no load-bearing step depends on a self-citation by the present authors. The only fragile point is Corollary 5.3's unproved assertion that Luby's deterministic coloring algorithm works unchanged on arbitrary sorted palettes of size deg(v)+1; this is an unsupported external black-box claim and would be a correctness gap if false, but it is not circular because the assertion is about the cited algorithm's specification, not a re-use of the paper's own target theorem.

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

No free parameters are fitted. The only nonstandard loading assumption is the unproved list-coloring adaptation of Luby's algorithm; all other assumptions are standard PRAM/model conventions. No new entities are introduced.

assumptions (5)

domain assumption The standard work-depth model on a common CRCW PRAM with Θ(log n)-bit words; arithmetic, comparison, and bitwise operations cost one step.
Invoked in Section 2 and throughout as the model of computation.
domain assumption The input is a simple graph with adjacency arrays for each vertex and n,m as stated.
Section 2 defines the input representation; all complexity counts assume this representation.
standard math Prefix sums, filtering, and stable integer sorting can be implemented within the stated O(k) work and O(log k) depth bounds.
Section 2 and Lemma 2.1 provide references; standard PRAM primitives.
ad hoc to paper Luby's deterministic coloring algorithm [Lub93] works without modification on list-coloring instances where each vertex has an arbitrary sorted palette of size deg(v)+1.
Corollary 5.3's last paragraph asserts this adaptation with no proof or citation; needed to solve residual instances in the bootstrapping.
standard math The pairwise-independent sample space x_u(r)=⊕_t u_t r_t with seed length ℓ=⌈log n⌉ is sufficient to derandomize the benefit problem; real-valued benefit arithmetic is exact.
Section 3.2 proves the needed properties; the applications use integer edge counts, so exact arithmetic is available.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Truly Work-efficient Parallel Deterministic $(\Delta+1)$-coloring and Maximal Independent Set." pith.science (2026). https://pith.science/paper/PL3VDPG3

@misc{pith2026260808296,
  author       = {Pith},
  title        = {Pith review of: Truly Work-efficient Parallel Deterministic $(\Delta+1)$-coloring and Maximal Independent Set},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PL3VDPG3}},
  note         = {Machine review of arXiv:2608.08296}
}

abstract

We give deterministic parallel algorithms that compute a $(\Delta+1)$-coloring and a maximal independent set for a simple graph with $n$ vertices and $m$ edges in $O(n+m)$ work and $O(\mathrm{poly}\log n)$ depth.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 38 canonical work pages

[1]

and Ramachandran, Vijaya , title =

Karp, Richard M. and Ramachandran, Vijaya , title =. Handbook of Theoretical Computer Science, Volume

work page
[2]

and Wigderson, Avi , title =

Karp, Richard M. and Wigderson, Avi , title =. 1985 , doi =

work page 1985
[3]

A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem , journaltitle =

Alon, Noga and Babai, L. A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem , journaltitle =. 1986 , doi =

work page 1986
[4]

1986 , doi =

Luby, Michael , title =. 1986 , doi =

work page 1986
[5]

1986 , doi =

Cole, Richard and Vishkin, Uzi , title =. 1986 , doi =

work page 1986
[6]

and Plotkin, Serge A

Goldberg, Andrew V. and Plotkin, Serge A. and Shannon, Gregory E. , title =. 1988 , keywords =

work page 1988
[7]

1993 , doi =

Luby, Michael , title =. 1993 , doi =

work page 1993
[8]

and Spencer, Thomas H

Goldberg, Mark K. and Spencer, Thomas H. , title =. 1989 , doi =

work page 1989

Show all 41 references

[9]

1994 , doi =

Kelsen, Pierre , title =. 1994 , doi =

1994
[10]

1996 , doi =

Han, Yijie , title =. 1996 , doi =

1996
[11]

1991 , doi =

Berger, Bonnie and Rompel, John , title =. 1991 , doi =

1991
[12]

1994 , keywords =

Motwani, Rajeev and Naor, Joseph and Naor, Moni , title =. 1994 , keywords =

1994
[13]

1992 , doi =

Linial, Nathan , title =. 1992 , doi =

1992
[14]

1996 , keywords =

Panconesi, Alessandro and Srinivasan, Aravind , title =. 1996 , keywords =

1996
[15]

Proceedings of the Twenty-Seventh Annual ACM--SIAM Symposium on Discrete Algorithms , series =

Ghaffari, Mohsen , title =. Proceedings of the Twenty-Seventh Annual ACM--SIAM Symposium on Discrete Algorithms , series =. 2016 , keywords =

2016
[16]

1988 , doi =

Cole, Richard , title =. 1988 , doi =

1988
[17]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , series =

Ghaffari, Mohsen and Kuhn, Fabian and Maus, Yannic , title =. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , series =. 2017 , keywords =

2017
[18]

, title =

Blelloch, Guy E. , title =. 1996 , doi =

1996
[19]

31st International Symposium on Distributed Computing , series =

Censor-Hillel, Keren and Parter, Merav and Schwartzman, Gregory , title =. 31st International Symposium on Distributed Computing , series =. 2017 , doi =

2017
[20]

and Kuhn, Fabian , title =

Ghaffari, Mohsen and Harris, David G. and Kuhn, Fabian , title =. 59th IEEE Annual Symposium on Foundations of Computer Science , series =. 2018 , doi =. 1711.02194 , eprinttype =

2018 arXiv
[21]

Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization , booktitle =

Rozho. Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization , booktitle =. 2020 , eprint =

2020
[22]

62nd IEEE Annual Symposium on Foundations of Computer Science , series =

Ghaffari, Mohsen and Kuhn, Fabian , title =. 62nd IEEE Annual Symposium on Foundations of Computer Science , series =. 2021 , doi =. 2011.04511 , eprinttype =

2021 arXiv
[23]

Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization , booktitle =

Ghaffari, Mohsen and Grunau, Christoph and Haeupler, Bernhard and Ilchi, Saeed and Rozho. Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization , booktitle =. 2023 , eprint =

2023
[24]

Local Distributed Rounding: Generalized to

Faour, Salwa and Ghaffari, Mohsen and Grunau, Christoph and Kuhn, Fabian and Rozho. Local Distributed Rounding: Generalized to. Proceedings of the 2023 ACM--SIAM Symposium on Discrete Algorithms , series =. 2023 , keywords =

2023
[25]

65th IEEE Annual Symposium on Foundations of Computer Science , series =

Ghaffari, Mohsen and Grunau, Christoph , title =. 65th IEEE Annual Symposium on Foundations of Computer Science , series =. 2024 , doi =. 2410.19516 , eprinttype =

2024 arXiv
[26]

Work-Efficient Parallel Derandomization

Ghaffari, Mohsen and Grunau, Christoph and Rozho. Work-Efficient Parallel Derandomization. 64th IEEE Annual Symposium on Foundations of Computer Science , series =. 2023 , eprint =

2023
[27]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing , series =

Ghaffari, Mohsen and Grunau, Christoph , title =. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , series =. 2024 , eprint =

2024
[28]

2024 IEEE International Parallel and Distributed Processing Symposium , series =

Coy, Sam and Czumaj, Artur and Davies-Peck, Peter and Mishra, Gopinath , title =. 2024 IEEE International Parallel and Distributed Processing Symposium , series =. 2024 , keywords =

2024
[29]

2026 , keywords =

Coy, Sam and Czumaj, Artur and Davies-Peck, Peter and Mishra, Gopinath , title =. 2026 , keywords =

2026
[30]

66th IEEE Annual Symposium on Foundations of Computer Science , series =

Ghaffari, Mohsen and Grunau, Christoph , title =. 66th IEEE Annual Symposium on Foundations of Computer Science , series =. 2025 , eprint =

2025
[31]

, title =

Harris, David G. , title =. 2023 , doi =. 1909.08065 , eprinttype =

2023 arXiv
[32]

, title =

Harris, David G. , title =. 2019 , eprint =

2019
[33]

2026 , eprint =

Hutton, Chase and Melrod, Adam , title =. 2026 , eprint =

2026
[34]

, title =

Harris, David G. , title =. 2019 , doi =. 1711.08494 , eprinttype =

2019 arXiv
[35]

and Fineman, Jeremy T

Blelloch, Guy E. and Fineman, Jeremy T. and Shun, Julian , title =. Proceedings of the Twenty-Fourth Annual ACM Symposium on Parallelism in Algorithms and Architectures , series =. 2012 , doi =. 1202.3205 , eprinttype =

2012 arXiv
[36]

Bhatt, P. C. P. and Diks, K. and Hagerup, T. and Prasad, V. C. and Radzik, T. and Saxena, S. , title =. 1991 , doi =

1991
[37]

1999 , doi =

Han, Yijie and Igarashi, Yoshihide , title =. 1999 , doi =

1999
[38]

Han, Yijie , title =
[39]

Proceedings of the Twenty-Ninth Annual

Fischer, Manuela and Noever, Andreas , title =. Proceedings of the Twenty-Ninth Annual
[40]

An Introduction to Parallel Algorithms , publisher =

J. An Introduction to Parallel Algorithms , publisher =
[41]

, title =

Brent, Richard P. , title =

Pith tools

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

[1] [1]

and Ramachandran, Vijaya , title =

Karp, Richard M. and Ramachandran, Vijaya , title =. Handbook of Theoretical Computer Science, Volume

work page

[2] [2]

and Wigderson, Avi , title =

Karp, Richard M. and Wigderson, Avi , title =. 1985 , doi =

work page 1985

[3] [3]

A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem , journaltitle =

Alon, Noga and Babai, L. A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem , journaltitle =. 1986 , doi =

work page 1986

[4] [4]

1986 , doi =

Luby, Michael , title =. 1986 , doi =

work page 1986

[5] [5]

1986 , doi =

Cole, Richard and Vishkin, Uzi , title =. 1986 , doi =

work page 1986

[6] [6]

and Plotkin, Serge A

Goldberg, Andrew V. and Plotkin, Serge A. and Shannon, Gregory E. , title =. 1988 , keywords =

work page 1988

[7] [7]

1993 , doi =

Luby, Michael , title =. 1993 , doi =

work page 1993

[8] [8]

and Spencer, Thomas H

Goldberg, Mark K. and Spencer, Thomas H. , title =. 1989 , doi =

work page 1989