arxiv: 2605.07644 · v1 · submitted 2026-05-08 · 💻 cs.DS

Recognition: no theorem link

Faster Deterministic Streaming Vertex Coloring

Hongyi Chen, Shiri Chechik, Tianyi Zhang

Pith reviewed 2026-05-11 02:04 UTC · model grok-4.3

classification 💻 cs.DS

keywords deterministic streamingvertex coloringsemi-streaminggraph coloringpass complexitymaximum degreeO(Delta) coloring

0 comments

The pith

A deterministic semi-streaming algorithm produces an O(Δ)-coloring after O(√log Δ) passes over the edge stream.

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

The paper constructs a deterministic algorithm for vertex coloring in the semi-streaming model, where edges arrive in arbitrary order and only linear memory is allowed. It achieves an O(Δ)-coloring in O(√log Δ) passes, improving the previous best deterministic bound of O(log Δ) passes for the same number of colors. Randomized algorithms reach (Δ+1) colors in a single pass, so this work narrows the gap by showing that sublogarithmic passes suffice deterministically for linear-in-Δ palette size. A sympathetic reader would care because the result resolves an open question on whether such trade-offs are possible and demonstrates that determinism need not force either many more colors or logarithmically many passes.

Core claim

In this paper, we present a new deterministic semi-streaming algorithm that computes an O(Δ)-coloring in O(√log Δ) passes. This is the first deterministic streaming algorithm to achieve a coloring with palette size linear-in-Δ using sublogarithmic-in-Δ passes.

What carries the argument

The new multi-pass deterministic construction that reduces the required number of passes over the edge stream from O(log Δ) to O(√log Δ) while maintaining an O(Δ)-coloring and linear memory.

If this is right

The deterministic trade-off between passes and colors for streaming vertex coloring improves to O(√log Δ) passes for O(Δ) colors.
Sublogarithmic passes now suffice for linear-in-Δ color counts in the deterministic semi-streaming setting.
The exponential separation between randomized and deterministic single-pass coloring can be bridged with fewer passes than previously shown.
Better concrete algorithms exist for deterministic coloring when multiple passes over the stream are feasible.

Where Pith is reading between the lines

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

The construction might be iterated or refined to reach polyloglog or constant passes while retaining O(Δ) colors.
Similar multi-pass derandomization ideas could apply to other streaming graph problems such as edge coloring or maximal independent sets.
For graphs where Δ is moderate, the reduced pass count makes deterministic coloring more practical in settings that avoid randomness.
The result suggests a gradual continuum of trade-offs exists between one-pass randomized methods and multi-pass deterministic ones.

Load-bearing premise

The semi-streaming model assumptions hold, including arbitrary edge order and linear memory, and the multi-pass construction correctly produces a valid O(Δ)-coloring without exceeding the stated bounds.

What would settle it

An explicit n-vertex graph with maximum degree Δ presented as an edge stream on which the algorithm either fails to produce a valid O(Δ)-coloring, requires more than O(√log Δ) passes, or uses superlinear memory.

read the original abstract

Graph coloring is a fundamental problem in computer science. In the semi-streaming model, an input graph $G$ on $n$ vertices and maximum degree $\Delta$ is presented as a stream of edges, and the goal is to compute a vertex coloring using a small number of colors while storing only $\tilde{O}(n)$ bits of memory. Recent work has revealed an exponential separation between randomized and deterministic approaches in this setting: while randomized algorithms can achieve a $(\Delta+1)$-coloring in a single pass [Assadi, Chen, and Khanna, 2019], any single-pass deterministic algorithm requires $\exp(\Delta^{\Omega(1)})$ colors [Assadi, Chen, and Sun, 2022]. Consequently, deterministic algorithms that use few colors must necessarily make multiple passes over the stream. Prior to this work, the best known deterministic trade-offs were: an $O(\Delta^2)$-coloring in 2 passes, an $O(\Delta)$-coloring in $O(\log \Delta)$ passes [Assadi, Chen, and Sun, 2022], and a $(\Delta+1)$-coloring in $O(\log \Delta \cdot \log\log \Delta)$ passes [Assadi, Chakrabarti, Ghosh, and Stoeckl, 2023]. It remained open whether better trade-offs -- particularly with sub-logarithmic pass complexity and linear-in-$\Delta$ palette size -- were achievable. In this paper, we present a new deterministic semi-streaming algorithm that computes an $O(\Delta)$-coloring in $O(\sqrt{\log \Delta})$ passes. This is the first deterministic streaming algorithm to achieve a coloring with palette size linear-in-$\Delta$ using sublogarithmic-in-$\Delta$ passes.

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.

Desk Editor's Note private letter to a colleague

This paper improves the deterministic semi-streaming O(Δ)-coloring bound from O(log Δ) passes to O(√log Δ) passes via an iterative multi-pass refinement.

read the letter

The main takeaway is that Chechik, Chen, and Zhang give a deterministic semi-streaming algorithm for an O(Δ)-coloring that uses only O(√log Δ) passes. This is a concrete step past the O(log Δ) passes that were the prior state for the same palette size, while still staying within Õ(n) memory and the arbitrary-order edge stream model. The construction works by iteratively building partial colorings and refining them across phases, where each phase reduces the effective degree bound by a polynomial factor in a constant number of passes. The overall pass count then follows from a recurrence on the logarithm of the current degree, which yields the square-root dependence. They keep memory linear by storing only per-vertex color lists plus a few auxiliary sketches. The full manuscript lays out the recurrence and the correctness argument without internal contradictions in the bounds or the validity of the final coloring. The approach is a natural extension of earlier degree-reduction ideas, but the specific phase design and recurrence analysis produce the improved trade-off. One minor soft spot is that the result remains logarithmic in character rather than constant-pass, and it inherits some machinery from the cited prior deterministic works, so the advance is incremental rather than a complete break from existing techniques. Still, the claimed bounds appear to hold up under the described construction. This paper is aimed at people working on streaming and distributed graph algorithms who track the deterministic-randomized separation in coloring. Anyone following the recent line of multi-pass deterministic results will get direct value from the new trade-off point. It is worth sending to peer review; the problem is central, the improvement is clear, and the evidence in the manuscript is solid enough to merit referee attention.

Referee Report

2 major / 3 minor

Summary. The paper presents a deterministic semi-streaming algorithm for vertex coloring on n-vertex graphs of maximum degree Δ. It computes an O(Δ)-coloring using O(√log Δ) passes over an arbitrary edge stream while storing only Õ(n) bits of memory. The algorithm proceeds via iterative multi-pass refinement: it maintains partial colorings and auxiliary sketches, with each phase using a constant number of passes to reduce the effective degree bound by a polynomial factor. The overall pass complexity then follows from solving the resulting recurrence on the degree parameter.

Significance. If the construction and analysis hold, this closes a gap in the deterministic-vs-randomized separation for streaming coloring by achieving the first sub-logarithmic pass bound for linear-in-Δ palette size. Prior deterministic results required Θ(log Δ) passes for O(Δ) colors. The explicit multi-phase degree-reduction technique and the recurrence-based pass analysis constitute a clear technical contribution; the Õ(n)-space implementation via per-vertex color lists and sketches is also a strength.

major comments (2)

[§4.2] §4.2, recurrence (4): the claimed O(√log Δ) bound assumes that each phase reduces the current degree bound from d to d^{1-ε} using O(1) passes with ε independent of d. The proof sketch must explicitly verify that the constant hidden in O(1) does not grow with the number of phases, otherwise the total pass count could revert to O(log Δ).
[§5] §5, Lemma 5.3: the correctness argument that the final coloring is proper and uses O(Δ) colors relies on the invariant that uncolored vertices have degree at most the current bound. It is unclear whether the auxiliary sketches used to detect conflicts across passes preserve this invariant with high probability or deterministically; a concrete failure probability or deterministic guarantee is needed.

minor comments (3)

[§3] The notation for the current degree bound (sometimes d, sometimes Δ_i) is used inconsistently between the algorithm description and the recurrence; a single global symbol would improve readability.
[Figure 1] Figure 1 (phase diagram) does not label the number of passes per phase; adding this annotation would make the recurrence derivation easier to follow.
[Table 1] The comparison table (Table 1) omits the recent (Δ+1)-coloring result of Assadi et al. 2023; including it would better contextualize the new trade-off.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and the precise technical comments. These have helped us strengthen the presentation. We address each major comment below, with revisions made to improve clarity in the relevant sections.

read point-by-point responses

Referee: [§4.2] §4.2, recurrence (4): the claimed O(√log Δ) bound assumes that each phase reduces the current degree bound from d to d^{1-ε} using O(1) passes with ε independent of d. The proof sketch must explicitly verify that the constant hidden in O(1) does not grow with the number of phases, otherwise the total pass count could revert to O(log Δ).

Authors: We agree the original proof sketch was too brief on this point. Each phase uses a fixed number of passes (independent of both the current degree bound d and the phase index) to achieve the degree reduction. The recurrence is solved by observing that the per-phase overhead remains bounded by the same constant throughout, yielding the claimed O(√log Δ) total. In the revised manuscript we have expanded Section 4.2 with an explicit inductive argument and a short calculation confirming the constant does not accumulate with the number of phases. revision: yes
Referee: [§5] §5, Lemma 5.3: the correctness argument that the final coloring is proper and uses O(Δ) colors relies on the invariant that uncolored vertices have degree at most the current bound. It is unclear whether the auxiliary sketches used to detect conflicts across passes preserve this invariant with high probability or deterministically; a concrete failure probability or deterministic guarantee is needed.

Authors: The algorithm is fully deterministic. The auxiliary sketches are deterministic constructions that exactly maintain the required degree invariant for uncolored vertices at the start of each phase; they detect conflicts without any randomness. Consequently the final coloring is proper and uses O(Δ) colors with certainty. We have revised the proof of Lemma 5.3 to state this deterministic guarantee explicitly and to walk through how the sketches preserve the invariant step by step. revision: yes

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper presents an explicit multi-pass deterministic construction for O(Δ)-coloring. The O(√log Δ) pass bound is obtained from a recurrence in which each phase uses O(1) passes to reduce the effective degree by a polynomial factor, with memory bounded by storing per-vertex color lists and auxiliary sketches. This follows directly from the algorithmic description and recurrence without any reduction to fitted parameters, self-definitional equations, or load-bearing self-citations. Prior results are cited only for context and comparison; the new bounds and correctness argument are independent of those citations.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on standard definitions of the semi-streaming model and graph coloring; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

domain assumption Semi-streaming model: edges arrive in arbitrary order, algorithm uses Õ(n) memory, graph has n vertices and max degree Δ.
Stated in the abstract as the setting for the algorithm.

pith-pipeline@v0.9.0 · 5628 in / 1202 out tokens · 34512 ms · 2026-05-11T02:04:22.876664+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

[1]

Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems , pages =

Coloring in graph streams via deterministic and adversarially robust algorithms , author =. Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems , pages =. 2023 , timestamp =. doi:10.1145/3584372.3588681 , _bib2doi_selected =

work page doi:10.1145/3584372.3588681 2023
[2]

Proceedings of the 39th Symposium on Principles of Distributed Computing , pages =

Simple, deterministic, constant-round coloring in the congested clique , author =. Proceedings of the 39th Symposium on Principles of Distributed Computing , pages =. 2020 , timestamp =. doi:10.1145/3382734.3405751 , _bib2doi_selected =

work page doi:10.1145/3382734.3405751 2020
[3]

Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages =

Deterministic graph coloring in the streaming model , author =. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages =. 2022 , timestamp =. doi:10.1145/3519935.3520016 , _bib2doi_selected =

work page doi:10.1145/3519935.3520016 2022
[4]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =

Concentration bounds for almost k-wise independence with applications to non-uniform security , author =. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =. 2021 , organization =. doi:10.1137/1.9781611976465.143 , _bib2doi_selected =

work page doi:10.1137/1.9781611976465.143 2021
[5]

Random Structures & Algorithms , volume =

Simple constructions of almost k-wise independent random variables , author =. Random Structures & Algorithms , volume =. 1992 , publisher =. doi:10.1002/rsa.3240030308 , _bib2doi_selected =

work page doi:10.1002/rsa.3240030308 1992
[6]

Approximation, Randomization, and Combinatorial Optimization

Tight Chernoff-Like Bounds Under Limited Independence , author =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques,. 2022 , organization =. doi:10.4230/LIPIcs.APPROX/RANDOM.2022.15 , publisher =

work page doi:10.4230/lipics.approx/random.2022.15 2022
[7]

Proceedings of the 9th Annual

Universal Classes of Hash Functions (Extended Abstract) , author =. Proceedings of the 9th Annual. 1977 , timestamp =. doi:10.1145/800105.803400 , publisher =

work page doi:10.1145/800105.803400 1977
[8]

Lecture 6: Streaming Algorithms , year =

work page
[9]

1982 , publisher =

Jayadev Misra and David Gries , title =. 1982 , publisher =. doi:10.1016/0167-6423(82)90012-0 , journal =

work page doi:10.1016/0167-6423(82)90012-0 1982
[10]

2018 , eprint =

Coloring in Graph Streams , author =. 2018 , eprint =. doi:10.48550/arXiv.1807.07640 , timestamp =

work page doi:10.48550/arxiv.1807.07640 2018
[11]

Proceedings of the Thirtieth Annual

Sepehr Assadi and Yu Chen and Sanjeev Khanna , title =. Proceedings of the Thirtieth Annual. 2019 , publisher =. doi:10.1137/1.9781611975482.48 , url =

work page doi:10.1137/1.9781611975482.48 2019
[12]

and Chakrabarti, Amit and Ghosh, Prantar , title =

Bera, Suman K. and Chakrabarti, Amit and Ghosh, Prantar , title =. 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) , pages =. 2020 , volume =. doi:10.4230/LIPIcs.ICALP.2020.11 , annote =

work page doi:10.4230/lipics.icalp.2020.11 2020
[13]

Topics from the Theory of Numbers , year =

Grosswald, Emil , title =. Topics from the Theory of Numbers , year =. doi:10.1007/978-0-8176-4838-1_9 , url =

work page doi:10.1007/978-0-8176-4838-1_9
[14]

Streaming algorithms for the missing item finding problem , booktitle =

Manuel Stoeckl , editor =. Streaming algorithms for the missing item finding problem , booktitle =. 2023 , url =. doi:10.1137/1.9781611977554.ch32 , timestamp =

work page doi:10.1137/1.9781611977554.ch32 2023
[15]

The Complexity of (

Yi. The Complexity of (. Proceedings of the 2019. 2019 , url =. doi:10.1145/3293611.3331607 , timestamp =

work page doi:10.1145/3293611.3331607 2019
[16]

(Delta+1) Coloring in the Congested Clique Model , booktitle =

Merav Parter , editor =. (Delta+1) Coloring in the Congested Clique Model , booktitle =. 2018 , url =. doi:10.4230/LIPIcs.ICALP.2018.160 , timestamp =

work page doi:10.4230/lipics.icalp.2018.160 2018
[17]

32nd International Symposium on Distributed Computing,

Merav Parter and Hsin. 32nd International Symposium on Distributed Computing,. 2018 , url =. doi:10.4230/LIPIcs.DISC.2018.39 , timestamp =

work page doi:10.4230/lipics.disc.2018.39 2018
[18]

Optimal (Degree+1)-Coloring in Congested Clique , booktitle =

Sam Coy and Artur Czumaj and Peter Davies and Gopinath Mishra , editor =. Optimal (Degree+1)-Coloring in Congested Clique , booktitle =. 2023 , url =. doi:10.4230/LIPIcs.ICALP.2023.46 , timestamp =

work page doi:10.4230/lipics.icalp.2023.46 2023
[19]

2008 , url =

Anna Pagh and Rasmus Pagh , title =. 2008 , url =. doi:10.1137/060658400 , timestamp =

work page doi:10.1137/060658400 2008
[20]

The Bit Extraction Problem of t-Resilient Functions (Preliminary Version) , booktitle =

Benny Chor and Oded Goldreich and Johan H. The Bit Extraction Problem of t-Resilient Functions (Preliminary Version) , booktitle =. 1985 , url =. doi:10.1109/SFCS.1985.55 , timestamp =

work page doi:10.1109/sfcs.1985.55 1985
[21]

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

Noga Alon and L. A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem , journal =. 1986 , url =. doi:10.1016/0196-6774(86)90019-2 , timestamp =

work page doi:10.1016/0196-6774(86)90019-2 1986
[22]

1993 , url =

Joseph Naor and Moni Naor , title =. 1993 , url =. doi:10.1137/0222053 , timestamp =

work page doi:10.1137/0222053 1993
[23]

Woodruff , title =

Piotr Indyk and David P. Woodruff , title =. 44th Symposium on Foundations of Computer Science,. 2003 , url =. doi:10.1109/SFCS.2003.1238202 , timestamp =

work page doi:10.1109/sfcs.2003.1238202 2003
[24]

ACM Journal of the ACM (JACM) , volume =

A framework for adversarially robust streaming algorithms , author =. ACM Journal of the ACM (JACM) , volume =. 2022 , publisher =. doi:10.1145/3498334 , _bib2doi_selected =

work page doi:10.1145/3498334 2022
[25]

13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , pages =

Chakrabarti, Amit and Ghosh, Prantar and Stoeckl, Manuel , title =. 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , pages =. 2022 , volume =. doi:10.4230/LIPIcs.ITCS.2022.37 , annote =

work page doi:10.4230/lipics.itcs.2022.37 2022
[26]

Naidu and Janani Sundaresan , title =

Sepehr Assadi and Christian Konrad and Kheeran K. Naidu and Janani Sundaresan , title =. 2024 , isbn =. doi:10.1145/3618260.3649763 , booktitle =

work page doi:10.1145/3618260.3649763 2024
[27]

ACM Trans

Henzinger, Monika and Peng, Pan , title =. ACM Trans. Algorithms , month =. 2022 , issue_date =. doi:10.1145/3501403 , abstract =

work page doi:10.1145/3501403 2022
[28]

Liu and Shay Solomon , title =

Sayan Bhattacharya and Fabrizio Grandoni and Janardhan Kulkarni and Quanquan C. Liu and Shay Solomon , title =. 2022 , url =. doi:10.1145/3494539 , timestamp =

work page doi:10.1145/3494539 2022
[29]

Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time , booktitle =

Soheil Behnezhad and Mahsa Derakhshan and MohammadTaghi Hajiaghayi and Cliff Stein and Madhu Sudan , editor =. Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time , booktitle =. 2019 , url =. doi:10.1109/FOCS.2019.00032 , timestamp =

work page doi:10.1109/focs.2019.00032 2019
[30]

Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time , booktitle =

Shiri Chechik and Tianyi Zhang , editor =. Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time , booktitle =. 2019 , url =. doi:10.1109/FOCS.2019.00031 , timestamp =

work page doi:10.1109/focs.2019.00031 2019
[31]

Maintaining exact distances under multiple edge failures

Sepehr Assadi and Pankaj Kumar and Parth Mittal , title =. 2022 , isbn =. doi:10.1145/3519935.3520005 , booktitle =

work page doi:10.1145/3519935.3520005 2022
[32]

A simple parallel algorithm for the maximal independent set problem , author =. SIAM J. Comput. , year =. doi:10.1137/0215074 , _bib2doi_selected =

work page doi:10.1137/0215074