{"id":"246b17d9-16c7-403c-b80e-3f66f748cf3f","arxiv_id":"2504.16470","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A W-streaming edge coloring algorithm uses O(delta to the 4/3 plus epsilon) colors with near-linear space, improving the prior randomized delta to 1.5 bound and giving the first deterministic subquadratic result.","lead":"The paper gives a streaming algorithm that colors graph edges using about delta to the 4/3 plus epsilon colors instead of the previous delta to 1.5, using near-linear memory. It also gives the first deterministic streaming edge coloring that breaks the quadratic color bound.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.1's recursive boosting is load-bearing for the randomized main theorem but only sketched; a single-pass pipelined implementation is never given, so the W-streaming feasibility of the reduction is unverified.","rationale":"I agree with the reader that Lemma 3.1 is the most load-bearing unverified step. The paper's main randomized theorem depends on boosting a partial coloring to a full coloring, and the proof sketch is one sentence. My own reading suggests the pipelining construction is likely valid: each copy of A is a streaming algorithm that can process its input online, so forwarding ⊥-edges to the next copy as they are identified simulates the recursion in a single pass, and linearity of expectation gives the geometric decay of uncolored edges. But the paper does not provide this construction, and a careful reviewer cannot certify Theorem 1.1 without it. I also note a secondary concrete discrepancy: Theorem 1.2 claims space O(n(log Δ)^{O(1/ε^4)}), while Lemma 4.1 proves O(n(log n)^{O(1/ε^4)}) and the small-Δ case stores the whole graph, requiring O(n log^{200/ε^4} n) space; replacing log n by log Δ is not justified by the proof. This weakens the deterministic space claim as stated, though the abstract's \\tilde{O}(n) space remains plausible. The pseudocode has minor typos (e.g., 'fq' in Algorithm 3 line 6) that do not affect correctness. Overall, the gaps are addressable and do not clearly invalidate the central claims, so the CONDITIONAL verdict is appropriate.","tokens_in":30127,"tokens_out":33622,"duration_ms":302397,"concrete_test":"Formalize the pipelined composition: for d = O(log Δ/δ), run d copies of A in series; for each incoming edge e, evaluate A_1(e); if A_1 outputs a color print it, else feed e to A_2, etc. Prove by induction that the expected number of uncolored edges after d levels is O(n) and that the final offline buffer fits in O(n) space, while total space is d·g(n,Δ) and total colors d·f(Δ). If this construction is valid, the concern is resolved; if it fails (e.g., because A's state cannot be advanced without seeing the full substream), Theorem 1.1 is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3, 'Reduction to Partial Coloring' (Lemma 3.1), states that any randomized W-streaming algorithm A that colors a δ-fraction of edges, marking the rest ⊥, can be converted into a full edge-coloring algorithm B with O((log Δ/δ) f(Δ)) colors and O((log Δ/δ) g(n,Δ)) space, by 'recursively apply[ing] the streaming algorithm on all edges marked with ⊥.' In the W-streaming model the input stream is read once; uncolored edges are not re-readable unless explicitly stored, which would cost Ω(nΔ) space. The proof sketch does not specify how the recursion is implemented in a single pass. The natural fix is to run d = O(log Δ/δ) copies of A concurrently, feeding each edge to copy i+1 only if copy i outputs ⊥, and printing the first non-⊥ color. This pipelining is standard but is not described in the paper; if it cannot be made to work (for instance, because A must print a value for every edge immediately and the interleaving of outputs is constrained), then Theorem 1.1's conversion from partial to full coloring fails. The lemma is the only mechanism in the randomized section that turns a constant-fraction coloring into a full coloring; Lemmas 3.2 and 3.3 produce only partial colorings. Thus the central randomized claim, O(log Δ)^{O(1/ε)} n space and O(log Δ)^{O(1/ε)} Δ^{4/3+ε} colors, rests on this unverified reduction.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents randomized and deterministic W-streaming edge-coloring algorithms for simple graphs with maximum degree Δ. The randomized algorithm (Theorem 1.1) claims O((log Δ)^{O(1/ε)} n) space and O((log Δ)^{O(1/ε)} Δ^{4/3+ε}) colors in expectation, improving the previous O(Δ^{1.5})-color randomized bound. The deterministic algorithm (Theorem 1.2) claims O((log Δ)^{O(1/ε)} (1/ε)^{O(1/ε^3)} Δ^{4/3+ε}) colors and O(n (log Δ)^{O(1/ε^4)}) space. The technical approach combines a reduction from general to bipartite graphs, a degree-pair decomposition of the input stream, forest structures over batches with nested random color packages for the low-degree case, a palette-matrix method for the regular case, and a derandomization using bipartite expanders from multiplicity codes.","tokens_in":30420,"tokens_out":18114,"duration_ms":178082,"significance":"If the stated bounds are correct, the randomized result is a genuine polynomial improvement over the recent Δ^{1.5} upper bound, and the deterministic result would be the first near-linear-space deterministic streaming edge coloring with substantially fewer than Δ^2 colors. The use of multiplicity-code expanders for derandomization is a technically interesting contribution that goes beyond simply replacing random shifts by expanders in a black-box way. The paper also benefits from a clean high-level architecture: isolate the unbalanced and regular cases, solve each with partial colorings, and then boost. However, several load-bearing reduction and invariant proofs are only sketched, so the manuscript is not yet at the standard of a journal publication.","major_comments":[{"comment":"The proof of Lemma 3.1 is not a valid W-streaming construction as written. The text says to 'recursively apply the streaming algorithm on all edges marked with ⊥', but the W-streaming model allows only one pass, and uncolored edges are not re-readable unless stored, which would cost Ω(nΔ) space. The natural fix is to run O((log Δ)/δ) independent copies concurrently and feed each edge to copy i+1 only if copy i marks it ⊥, but this pipelining is not described, and the expected-fraction guarantee must be stated for arbitrary sub-instances rather than only for the original m edges. Since Lemmas 3.2 and 3.3 produce only partial colorings, Lemma 3.1 is the only mechanism in the randomized section that converts a constant-fraction coloring into a full coloring; without a complete proof of this reduction, Theorem 1.1 is not established.","section":"Section 3, Lemma 3.1"},{"comment":"The proof of Invariant 3.1(2) is incomplete in the case where the highest empty node W is the root of the tree (or more generally when the coordinate f_i equals Δ^ε). The displayed argument uses minimality of f_i to assert the existence of an alternate frequency vector with coordinate f_i/2, but if f_i = Δ^ε, then f_i/2 is not an admissible branching parameter, so the inequality for node N_i is not justified. This invariant is used in Lemma 3.6 to obtain the O((log Δ)^{O(1/ε)} n) space bound, so the gap is load-bearing for Theorem 1.1. Please either repair the proof for the root/highest-node case or weaken the invariant to apply only to marked nodes and derive the space bound directly.","section":"Section 3.1.3, Lemma 3.7 and Invariant 3.1(2)"},{"comment":"The deterministic space bound in Theorem 1.2 is not directly supported by the stated lemmas. Theorem 1.2 claims O(n (log Δ)^{O(1/ε^4)}) space, but Lemma 4.1 and Lemma 4.2 provide O(n (log n)^{O(1/ε^4)}) and O(n (log n)^{O(1/ε^3)}) space respectively, and the base case in §4.2.1 uses O(n log^{200/ε^4} n) space when Δ is small. Since log n can be much larger than log Δ, the theorem's bound in terms of log Δ does not follow as written. Please clarify whether space is measured in words or bits, and either adjust the theorem statement, prove that the (log n) factors can be replaced by (log Δ) factors under the stated assumptions, or add the base-case cost explicitly to the final complexity.","section":"Theorem 1.2 vs. Lemma 4.1 and §4.2.1"}],"minor_comments":[{"comment":"There are several typos and duplicated phrases: the abstract has 'pa irs', and Lemma 3.2 says 'Given an graph' and repeats 'for any constant ε > 0' twice. These should be cleaned up.","section":"Abstract and Lemma 3.2"},{"comment":"Line 2 of Algorithm 4 defines E_{x,y} using variables x_u and y_u that are not defined in the deterministic high-degree algorithm; this appears to be leftover from the randomized algorithm in Section 3.2. Please replace or remove this line.","section":"Algorithm 4 (Section 4.3.2)"},{"comment":"The proof of Lemma 4.10 is omitted with the remark that it is the same as before. This is an important space bound for the deterministic construction, and the deterministic version additionally stores tuple labels on marked nodes, so a few sentences explaining why the tuple storage does not change the asymptotic space would be helpful.","section":"Section 4.2.3, Lemma 4.10"},{"comment":"The sentence 'the total number of colors over all (l, r) would can be bounded' contains a grammatical error and should read 'can be bounded'.","section":"Proof of Theorem 1.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is a serious extension of the authors' own ICALP 2024 work and appears to be within the journal's scope. I do not see a circularity or novelty problem. The main risk is that the randomized section depends on reductions and invariants that are only sketched; the deterministic section also has a space-bound mismatch with the main theorem. These issues seem fixable within the manuscript's scope, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the paper is real: it breaks the Δ^{1.5} randomized barrier and gives the first deterministic subquadratic streaming edge coloring, at Δ^{4/3+ε} colors with near-linear space. The multi-layer forest allocation is a genuine extension of the SB24/CMZ24 approach, and the derandomization via multiplicity-code expanders is clever and nontrivial. Second, the biggest flagged risk—Lemma 3.1's recursion—is real but not fatal. The proof sketch says 'recursively apply the streaming algorithm on all edges marked ⊥' without saying how that runs in one pass. The standard answer is to pipeline O(log Δ/δ) copies of the partial-coloring algorithm, feeding edge e to copy i+1 exactly when copy i outputs ⊥. That preserves stream order and multiplies space by the depth. It would take a page to formalize, and the paper should include it because Lemma 3.1 carries the whole randomized section. But I don't see any obstruction.\n\nSoft spots, in proportion. The deterministic space bound is inconsistent: Theorem 1.2 promises O(n (log Δ)^{O(1/ε^4)}), but Lemma 4.1 gives O(n (log n)^{O(1/ε^4)}). That's a genuine mismatch, and the theorem as stated is stronger than the proof supports. The authors need to either prove the log Δ version or change Theorem 1.2. The pseudocode has small errors (Algorithm 4 references undefined xu,yu; Algorithm 1 has a typo in the loop variable). Minor. The paper also inherits a few typos like 'an graph.' All fixable.\n\nI did check the probability argument in Lemma 3.9; the 2/3 uniqueness bound and the (4/5)^h palette-survival bound are independent (Invariant 3.1(4) earns its keep), so the constant-fraction claim is coherent. Lemma 3.6's space bound for marked sets also checks out under the invariants.\n\nThe citation pattern is fine: building on SB24 and CMZ24 is appropriate, and the CMZ24 overlap is a published ICALP paper used as a building block, not as the conclusion.\n\nWho gets value: streaming algorithms researchers, and anyone tracking edge-coloring bounds. It deserves a serious referee. I would send it out and ask for a revision that (a) formalizes Lemma 3.1's pipelining, and (b) fixes the deterministic space statement. The core ideas look right to me.","headline":"Genuinely new Δ^{4/3+ε} streaming edge-coloring bounds, randomized and deterministic, with a thin-but-repairable reduction lemma and one real space-bound inconsistency.","tokens_in":30971,"tokens_out":5417,"would_cite":true,"duration_ms":47845,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","68W20","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"A W-streaming algorithm can properly edge-color a graph in near-linear space with Δ^{4/3+ε} colors, and deterministically so for the first time.","keywords":["edge coloring","W-streaming model","single-pass streaming algorithms","randomized algorithms","derandomization","bipartite expanders","multiplicity codes","near-linear space"],"falsifier":"Run the boosting lemma on a graph whose edges arrive in an adversarial order and whose partial-coloring subroutine colors fewer than half the edges; if a faithful one-pass implementation must either store the uncolored edge set or read the stream again to color them all, then the O(n)-space recursion fails on that instance. Concretely, an input that is a sequence of disjoint stars or a large matching that the subroutine leaves entirely uncolored would force the recursion to revisit Ω(m) edges, which no O(n)-space single-pass algorithm can do.","tokens_in":29899,"feed_emoji":"🎨","tokens_out":6764,"duration_ms":59163,"temperature":0.7,"pith_summary":"The paper claims that in the write-only streaming model, where a graph's edges arrive once in arbitrary order and the algorithm must emit colors as it goes, edge coloring can be done with far fewer colors than the previous quadratic and 3/2-power barriers while keeping near-linear memory. Specifically it proves a randomized algorithm using O((log Δ)^{O(1/ε)} n) space and O((log Δ)^{O(1/ε)} $Δ^{{4/3+ε}}$) colors, and a deterministic version with slightly worse polylogarithmic factors. A sympathetic reader would care because this is the first deterministic near-linear-space streaming coloring that bypasses the old O(Δ²) color bound, and it shows the bottleneck is not the output constraint but how batches of edges are organized. The insight is to color only a constant fraction of edges per pass and to recurse on the rest, while using nested random color packages indexed by batch frequencies so that unused colors around vertices can be represented compactly.","feed_headline":"Streaming edge coloring drops to Δ^{4/3+ε} colors in near-linear space","feed_subtitle":"First deterministic one-pass edge coloring with near-linear memory that uses far fewer than Δ² colors.","key_machinery":"The load-bearing object is a forest over the sequence of input batches whose branching factors encode how many incident edges a vertex accumulates at different time scales. On each forest, colors are allocated top-down as nested packages: a node's package is a disjoint union of the packages of its children, and the same small palette can be reused on many leaves. Each vertex keeps only the marked forest nodes that cover the batches where it previously used colors, and a random shift per low-side vertex lets most edges in a batch fall on distinct palette positions. In the high-degree regime the machinery switches to a table of palettes indexed by counters of batch appearances. For derandomization, the random shifts and package assignments are replaced by explicit unbalanced bipartite expanders from multiplicity codes, whose right-hand degree bound limits how often a palette recurs.","core_discovery":"The central claim, stated as Theorem 1.1, is that for any constant ε>0 there is a randomized W-streaming algorithm that properly edge-colors any simple graph of maximum degree Δ using O((log Δ)^{O(1/ε)} n) space and O((log Δ)^{O(1/ε)} $Δ^{{4/3+ε}}$) colors in expectation; Theorem 1.2 gives a deterministic version with O((log Δ)^{O(1/ε)}(1/ε)^{O(1/$ε^{3}$)} $Δ^{{4/3+ε}}$) colors and O(n (log Δ)^{O(1/$ε^{4}$)}) space. The proof splits edges by the degrees of their endpoints inside each batch, colors the unbalanced low-degree case with a hierarchy of nested palettes over a forest of batches, uses a color-table with random shifts for the balanced high-degree case, and derandomizes both with explicit bipartite expanders built from multiplicity codes. The previously known best randomized result used O($Δ^{{1.5}}$) colors; the deterministic state of the art was O(Δ²), so the 4/3 exponent is the paper's new polynomial improvement.","pith_inferences":["The same two-regime split (unbalanced versus balanced batches) might be applied to online or semi-streaming coloring, not just W-streaming, to get Δ^{4/3+ε} color bounds with sublinear memory.","A natural testable extension is to tune ε adaptively: since the color bound is O(Δ^{4/3+ε}), setting ε ≈ 1/log Δ gives roughly Δ^{4/3} polylog factors, and the proof suggests the constants degrade exponentially in 1/ε, so the practical break-even against Δ^{1.5} algorithms is worth benchmarking.","The paper leaves open whether the exponent 4/3 is an artifact of the balancing argument or a genuine barrier; a matching lower bound for one-pass W-streaming coloring with near-linear space would settle this.","Because the randomized algorithm's space bound holds only in expectation, a practical implementation would need tail bounds on the data structures; the deterministic theorem avoids that but at higher polylog cost."],"forward_implications":["Any graph with maximum degree Δ can be edge-colored in one streaming pass with near-linear memory and a palette of order Δ^{4/3+ε} colors, for every fixed ε>0.","The deterministic version, for the first time, breaks the quadratic Δ² color barrier in the W-streaming model without super-linear space.","The color count remains polynomial in Δ, not polylogarithmic, so the result is a tradeoff curve rather than a near-optimal Δ+1 coloring.","If the partial-coloring recursion is valid, the same boosting applies to any future algorithm that colors a constant fraction of edges, so better partial colorings immediately yield better full colorings at logarithmic color and space overhead.","The derandomization via multiplicity-code expanders shows that the randomness used here can be replaced without increasing space beyond polylogarithmic factors, which may transfer to other streaming coloring tasks."],"supporting_citations":[{"why":"Supplies the partial-coloring boosting lemma (Lemma 3.1) and the recursive scheme that turns a constant-fraction coloring into a full coloring with O(log Δ/δ) color and space overhead.","marker":"[CMZ24]"},{"why":"Establishes the previous randomized O(Δ^{1.5})-color W-streaming bound and the color-table approach with random shifts reused in Lemma 3.3.","marker":"[SB24]"},{"why":"Provides the deterministic general-to-bipartite reduction (Lemma 2.1) and the O(Δ²/s)-color tradeoff that the new result improves in the near-linear-space regime.","marker":"[GS24]"},{"why":"Supplies explicit unbalanced bipartite expanders from multiplicity codes, used in the derandomization and in the online perfect-matching building block.","marker":"[KTS22]"},{"why":"Gives the offline bipartite edge coloring used to color each palette subgraph in the high-degree case.","marker":"[COS01]"},{"why":"Gives the deterministic O(Δ²)-color near-linear-space baseline that Theorem 1.2 bypasses.","marker":"[Ansari, Saneian, and Zarrabi-Zadeh, 2022]"}],"fun_headline_variants":["First deterministic edge coloring below Δ² in streaming","Streaming edge coloring hits Δ^{4/3+ε} with near-linear space","Subquadratic deterministic edge coloring in one pass","Edge coloring: deterministic Δ^{4/3} beats quadratic bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument assumes that the constant-fraction partial coloring can be re-run on the remaining uncolored edges within one pass by restarting the algorithm on those edges, without storing them; if the W-streaming model does not allow re-reading uncolored edges, the recursive boosting step is unsupported.","fun_headline_variants_meta":{"raw":{"variants":["First deterministic edge coloring below Δ² in streaming","Streaming edge coloring hits Δ^{4/3+ε} with near-linear space","Subquadratic deterministic edge coloring in one pass","Edge coloring: deterministic Δ^{4/3} beats quadratic bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000203,"raw_usage":{"total_tokens":1458,"prompt_tokens":1088,"completion_tokens":370,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":704,"completion_tokens_details":{"reasoning_tokens":299}},"tokens_in":704,"tokens_out":370,"duration_ms":4183,"temperature":1.0,"reasoning_tokens":299,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:03:52.836267+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the boosting lemma on a graph whose edges arrive in an adversarial order and whose partial-coloring subroutine colors fewer than half the edges; if a faithful one-pass implementation must either store the uncolored edge set or read the stream again to color them all, then the O(n)-space recursion fails on that instance. Concretely, an input that is a sequence of disjoint stars or a large matching that the subroutine leaves entirely uncolored would force the recursion to revisit Ω(m) edges, which no O(n)-space single-pass algorithm can do.","supporting_citations":[{"cited_title":"Simple streaming algorithms for edge coloring","cited_arxiv_id":null,"evidence_quote":"Gives the deterministic O(Δ²)-color near-linear-space baseline that Theorem 1.2 bypasses."}],"review_version":1}