{"id":"a2d83ffb-89fb-4255-b63b-a7789e8aaec3","arxiv_id":"2412.12589","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An O(n)-bit randomized protocol for (Δ+1)-vertex coloring in O(log log n · log Δ) rounds, plus a deterministic O(n)-bit O(1)-round (2Δ-1)-edge coloring protocol and a matching Ω(n) lower bound.","lead":"This paper presents communication protocols for graph coloring where two players split the graph's edges. It achieves near-linear communication with substantially fewer rounds than prior work, and proves a matching communication lower bound for edge coloring.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.11's Chernoff bound is applied to the wrong event, leaving the O(n) expected communication of the vertex coloring protocol unproven.","rationale":"The reader identified Lemma 4.11 as the key weakness, and that is indeed the most load-bearing concern: the O(n) expected communication of the vertex coloring protocol hinges on the probability of a high-degree vertex becoming low-degree being at most 1/log^3 Δ. However, the reader's specific explanation is slightly inaccurate: the statement 'if more than a quarter idle, cannot become low-degree' is actually correct, because idle neighbors remain active and thus keep the vertex's active degree above the next threshold. The real flaw is that the Chernoff bound is applied to the wrong threshold: it bounds the probability that fewer than a quarter of the minimum possible active-neighbor count are idle, rather than fewer than a quarter of the actual count d. This is a genuine proof gap, but it is plausibly fixable by re-running the Chernoff argument with the actual d. I did not find problems in the edge coloring upper and lower bounds; the deterministic (2Δ−1)-edge coloring protocol and the ZEC lower bound appear internally consistent. A secondary concern is that Section 3.2's reduction to k-Slack-Int assumes disjoint forbidden color sets A and B, but two non-adjacent neighbors of a vertex can share a color, so A∩B may be nonempty; however, because |A|+|B| ≤ Δ < Δ+1, the key sampling test |S∩A|+|S∩B| < |S| still holds for S=[Δ+1], suggesting the protocol may survive with a corrected analysis. The primary blocker remains the Lemma 4.11 proof gap, so the verdict should remain CONDITIONAL pending a corrected concentration argument.","tokens_in":35795,"tokens_out":46536,"duration_ms":372596,"concrete_test":"Rewrite the proof of Lemma 4.11 conditioning on the actual active-neighbor count d ≥ Δ/2^{2i}, and verify Chernoff with mean d/2 and threshold d/4. Check that Pr[X < d/4] ≤ e^{-d/16} ≤ e^{-Δ/2^{2i+4}}; if this holds, update the proof accordingly and confirm Lemma 4.12's 1/log^3 Δ bound still follows for j = O(log log Δ). Alternatively, run a simulation of Random-Color-Trial on high-degree stars with Δ = 10^6 to measure the fraction of vertices becoming low-degree in the first O(log log Δ) iterations and compare with e^{-Δ/2^{2i+4}}.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The proof of Lemma 4.11 bounds Pr[X ≤ Δ/2^{2i+2}], where X is the number of idle active neighbors and Δ/2^{2i} is only a lower bound on the actual number d of active neighbors of a high-degree vertex. The bad event for becoming low-degree is X < d/4, which is strictly larger than X ≤ Δ/2^{2i+2} whenever d > Δ/2^{2i}. A Chernoff upper bound on the smaller event does not bound the larger event, so the claimed probability e^{-Δ/2^{2i+4}} does not follow from the argument as written. The lemma is repairable by applying Chernoff to the actual d, giving Pr[X < d/4] ≤ e^{-d/16} ≤ e^{-Δ/2^{2i+4}}, but the current proof is incomplete. Since Lemma 4.12 and hence Lemma 4.8 depend on this bound to make the expected Color-Sampling cost O(1) per high-degree vertex, Theorem 1's O(n) expected communication claim is not established by the text as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies two-party communication protocols for graph coloring. It presents a randomized (Δ+1)-vertex-coloring protocol with O(n) expected bits and O(log log n · log Δ) worst-case rounds, improving on the O(n)-round protocol of Flin and Mittal; a deterministic (2Δ−1)-edge-coloring protocol with O(n) bits and O(1) rounds; and an Ω(n)-bit lower bound for randomized (2Δ−1)-edge coloring with constant success probability, yielding a W-streaming space lower bound. The vertex-coloring protocol runs random color trials to leave O(n/log^4 n) uncolored vertices in expectation and then solves the leftover (degree+1)-list-coloring instance via palette sparsification. The edge-coloring protocol combines Vizing/Fournier-type decomposition, deferred subgraphs, matchings, and palette sharing. The lower bound is proved through a zero-communication edge-coloring game and Raz's parallel repetition theorem.","tokens_in":35952,"tokens_out":43035,"duration_ms":372853,"significance":"If the vertex-coloring analysis is completed, the results are significant: they give optimal communication with exponentially improved round complexity for vertex coloring, and they provide the first non-trivial communication protocol and matching lower bound for (2Δ−1)-edge coloring, plus a new space lower bound in the W-streaming model. The paper builds on published tools—Flin and Mittal's color sampling, Halldórsson et al.'s palette sparsification, Vizing's and Fournier's theorems, and Raz's parallel repetition—rather than on its own claims, and the edge-coloring protocol includes a welcome deterministic O(1)-round improvement. The lower-bound construction via the ZEC game is elegant and appears sound.","major_comments":[{"comment":"The Chernoff bound in Lemma 4.11 is applied to the wrong event. The proof lets X be the number of idle active neighbors and states that 'fewer than a quarter of the neighbors idle' is Pr[X ≤ (1−1/2)·Δ/2^{2i+1}] = Pr[X ≤ Δ/2^{2i+2}]. But if d denotes the actual number of active neighbors of a high-degree vertex, the bad event for becoming low-degree is X < d/4, and d/4 ≥ Δ/2^{2i+2}. The event X ≤ Δ/2^{2i+2} is strictly smaller than X < d/4 whenever d > Δ/2^{2i}, so an upper bound on the smaller event does not bound the larger event. Consequently the claimed bound e^{−Δ/2^{2i+4}} does not follow from the written argument, and since Lemma 4.12 and Lemma 4.8 depend on it, Theorem 1's O(n) expected communication is not established as written. The lemma is repairable by applying Chernoff to the actual d: with E[X]=d/2 and δ=1/2, Pr[X < d/4] ≤ e^{−d/16} ≤ e^{−Δ/2^{2i+4}}. The revision should state the correct event and this derivation explicitly.","section":"Section 4.3, Lemma 4.11"}],"minor_comments":[{"comment":"The phrase 'becomes low-degree in the ith iteration' is ambiguous about whether the transition is from iteration i to i+1 or from i−1 to i; the proof should fix the indexing, because the threshold changes as Δ/2^{2i} with i.","section":"Section 4.3, Lemma 4.11 / Lemma 4.12"},{"comment":"The displayed sum contains a typo: 'e^{−Δ/2^{2t+4}}' should use the same index as the summation, and the intermediate bound switches between 1/log^3 Δ and 1/log^4 Δ inconsistently; the final estimate is correct after fixing the exponents.","section":"Section 4.3, proof of Lemma 4.12"},{"comment":"The output line says 'Any element from X∩Y', but the problem k-Slack-Int asks for an element of [m] \\(X∪Y); this should be corrected.","section":"Appendix A, Algorithm 3"},{"comment":"Lemma 4.6 is stated as an inequality, but the displayed derivation actually gives an equality E[C_i] = Pr[A_i=1]·E[C_i|A_i=1]; this is a minor presentation issue.","section":"Section 4.3, Lemma 4.6"}],"recommendation":"major_revision","confidential_remarks":"The paper is promising and the main results are likely correct after a local, well-understood repair to Lemma 4.11. The lower-bound section and the edge-coloring upper bound appear sound on close reading, including the randomized-label argument in Lemma 6.2 once the 'contains only those colors' definition is used. I would not reject; the missing step in Lemma 4.11 is load-bearing but straightforward to fix within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a serious paper with two results that look right—a deterministic O(1)-round, O(n)-bit protocol for (2Δ−1)-edge coloring and a matching Ω(n) lower bound—plus a vertex coloring protocol that cuts the round complexity from O(n) to O(log log n·log Δ) while keeping O(n) expected communication. The edge coloring results are clean, and the ZEC game plus parallel repetition gives a genuinely new W-streaming space lower bound.\n\nThe main soft spot is Lemma 4.11 in the vertex coloring analysis. The proof says it bounds the probability that fewer than a quarter of a vertex's active neighbors are idle, but the Chernoff computation plugs in the lower bound Δ/2^{2i} for the actual active-neighbor count d. That produces a bound on Pr[X ≤ Δ/2^{2i+2}], which is not an upper bound on Pr[X < d/4] when d is larger. The stress-test is right about this: the proof as written doesn't establish the lemma. The good news is the repair is easy—apply Chernoff with the actual d to get Pr[X < d/4] ≤ e^{−d/16} ≤ e^{−Δ/2^{2i+4}}, and the rest of the argument goes through unchanged. So this is a genuine but localized gap, not a sign that the main claims are wrong. As it stands, Theorem 1's O(n) expected communication is not fully proven in the text; the authors need to fix this before publication.\n\nOne aside: the stress-test's own description of the bad event as X < d/4 is a bit loose—the event that actually makes a vertex low-degree is X < Δ/2^{2i+2}. The confusion doesn't change the verdict; the proof is still flawed as written.\n\nThe citation pattern is honest, and the paper credits Flin for the Lemma 5.4 improvement. I'd bring this to the reading group and cite the edge coloring results in my own work. It deserves a serious referee; the right outcome is conditional acceptance pending a corrected Lemma 4.11.","headline":"Strong edge coloring results, but the vertex coloring proof has a localized Chernoff gap that needs fixing before Theorem 1 is fully established.","tokens_in":36523,"tokens_out":11135,"would_cite":true,"duration_ms":80225,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","68Q17","68R10","68W20","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that (Δ+1)-vertex coloring and (2Δ−1)-edge coloring can both be solved in the two-party communication model with O(n) bits, the first with O(log log n · log Δ) rounds and the second with O(1) rounds, and that the…","keywords":["graph coloring","communication complexity","vertex coloring","edge coloring","random color trial","two-party protocols","W-streaming model","lower bounds"],"falsifier":"Run Algorithm 1 many times on a graph with one center vertex of degree Δ and Δ leaves, tracking the center's number of active neighbors after each of the first O(log log Δ) iterations; the O(n)-bit vertex-coloring claim depends on the empirical frequency of dropping below Δ/$2^{{2i}}$ being at most 1/log³Δ.","tokens_in":35566,"feed_emoji":"🎨","tokens_out":12960,"duration_ms":110151,"temperature":0.7,"pith_summary":"Two players, Alice and Bob, each hold part of a graph's edges. This paper gives a randomized protocol that finds a proper (Δ+1)-vertex coloring of any n-vertex graph of maximum degree Δ using O(n) bits of communication in expectation and O(log log n · log Δ) rounds in the worst case, and a deterministic protocol that finds a (2Δ−1)-edge coloring using O(n) bits and O(1) rounds. It also proves an Ω(n)-bit lower bound for any randomized (2Δ−1)-edge coloring protocol with success probability at least 1/2. Together these results make both coloring problems communication-optimal and round-efficient in the two-party model, where the previous vertex-coloring protocol achieved the same bit bound only at the cost of O(n) expected rounds.","feed_headline":"Graph coloring: O(n) bits and near-logarithmic rounds","feed_subtitle":"Vertex coloring keeps linear communication with far fewer rounds; edge coloring gets a deterministic O(1)-round protocol.","key_machinery":"The paper's vertex-coloring machine is the random color trial. In each iteration every active vertex is awake with probability 1/2 and uses the Color-Sample primitive to draw uniformly from its currently available colors; a vertex keeps its color only if no neighbor drew the same color, and the probability of staying active decays as (23/24)^i. The leftover instance is then handled by palette sparsification, which keeps O(log² Z) colors per vertex and leaves a sparse, still-colorable subproblem. For edge coloring the machine is a structural decomposition: deferring edges between vertices of degree at least Δ−1 produces a degree-2 subgraph; a Δ-perfect matching (whose existence follows from integrality of fractional matchings in bipartite graphs) covers all degree-Δ vertices; after these removals the remaining subgraph meets Fournier's independence condition and can be colored with Δ−1 colors locally. The lower-bound machine is a zero-communication game on a constant-size graph with Δ=2, where any no-communication strategy wins with probability at most 11024/11025, amplified to $2^{{−Ω(n)}}$ by parallel repetition.","core_discovery":"On the paper's own terms, the central discovery is that the linear-bit boundary for graph coloring does not force sequential behavior. The vertex-coloring protocol runs O(log log n) rounds of a random color trial in which active vertices independently sample available colors and keep them unless a neighbor collides; the leftover uncolored vertices form a degree+1-list coloring instance that is finished by palette sparsification. The edge-coloring protocol is fully deterministic: each player locally defers a degree-2 set of edges, removes a matching covering all degree-Δ vertices, and then applies Fournier's condition to color the remaining subgraph, while matching and deferred edges are colored with one shared special color or the other player's palette. The lower bound for (2Δ−1)-edge coloring is built from a constant-size zero-communication game on seven vertices and parallel repetition, and it carries over to a linear space lower bound for W-streaming algorithms.","pith_inferences":["A cheap check of the vertex-coloring analysis is to simulate the random color trial on a large star and count how often the center's active-neighbor count falls below Δ/2^{2i} in the first O(log log Δ) iterations; the protocol's O(n)-bit claim is false if that frequency is not O(1/log³Δ).","The constant-size game plus parallel-repetition template is not specific to 3-edge-coloring; it may yield Ω(n) communication lower bounds for other locally checkable labeling problems in the two-party model, such as maximal matching or sinkless orientation.","If a round-parallel available-color sampler could replace the binary-search-based Color-Sample, the vertex-coloring round bound would drop to O(log log n) with no change in the O(n) bit budget; the log Δ factor is an artifact of the sampling primitive.","The W-streaming lower bound says nothing yet about (Δ+1)-edge coloring, and adapting the ZEC-NEW construction to fewer colors would be a natural next step."],"forward_implications":["The (Δ+1)-vertex coloring protocol reaches the same O(n) expected communication as the earlier sequential protocol while cutting worst-case rounds from O(n) to O(log log n · log Δ).","The deterministic (2Δ−1)-edge coloring protocol uses O(n) bits and O(1) rounds, so edge coloring is solved with both optimal communication and constant round count.","The Ω(n) lower bound matches the O(n) upper bound, making the edge-coloring protocol communication-optimal up to constants, even against randomized protocols with constant success probability.","Corollary 1.2 gives the first nontrivial space lower bound for (2Δ−1)-edge coloring in the W-streaming model: any constant-pass randomized algorithm needs Ω(n) bits of space in expectation.","Because (2Δ)-edge coloring needs zero communication (Theorem 3), the 2Δ−1 color budget in the lower bound is the smallest one for which the problem is genuinely hard."],"supporting_citations":[{"why":"Supplies the Color-Sample subroutine and the earlier O(n)-bit, O(n)-round vertex coloring protocol that this paper improves.","marker":"[FM25]"},{"why":"Provides the palette sparsification theorem used to color the leftover uncolored vertices as a degree+1-list coloring instance.","marker":"[HKN+22]"},{"why":"Fournier's theorem is the condition under which the remaining subgraphs can be edge-colored with Δ−1 colors.","marker":"[Fou73]"},{"why":"Integrality of fractional matchings in bipartite graphs justifies existence of the Δ-perfect matching.","marker":"[Sch03]"},{"why":"Parallel repetition theorem amplifies the constant-size ZEC game lower bound to n independent instances.","marker":"[Raz98]"},{"why":"Simplified parallel repetition result used in the same amplification step of the lower bound.","marker":"[Hol09]"},{"why":"Converts a public-randomness protocol into one with only private randomness, a step in deriving the 2^{-o(n)} zero-communication simulation.","marker":"[New91]"}],"fun_headline_variants":["Vertex coloring drops to log-log rounds at same bit cost","Edge coloring: O(1) rounds, O(n) bits, deterministic","Linear-bit coloring now runs in O(log log n) rounds","Graph coloring: communication stays linear, rounds plummet","Deterministic edge coloring in O(1) rounds with O(n) bits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The vertex-coloring protocol's linear communication budget rests on the assumption that a vertex with many neighbors keeps a substantial number of them still uncolored through the early random-color-trial iterations; the paper needs the rare failures of this event to cost at most about 1/log³Δ probability per vertex, and if failures are more common the expected communication per vertex can blow up from constant to log²Δ.","fun_headline_variants_meta":{"raw":{"variants":["Vertex coloring drops to log-log rounds at same bit cost","Edge coloring: O(1) rounds, O(n) bits, deterministic","Linear-bit coloring now runs in O(log log n) rounds","Graph coloring: communication stays linear, rounds plummet","Deterministic edge coloring in O(1) rounds with O(n) bits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000747,"raw_usage":{"total_tokens":3372,"prompt_tokens":1031,"completion_tokens":2341,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":647,"completion_tokens_details":{"reasoning_tokens":2252}},"tokens_in":647,"tokens_out":2341,"duration_ms":15170,"temperature":1.0,"reasoning_tokens":2252,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T13:56:42.635142+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 many times on a graph with one center vertex of degree Δ and Δ leaves, tracking the center's number of active neighbors after each of the first O(log log Δ) iterations; the O(n)-bit vertex-coloring claim depends on the empirical frequency of dropping below Δ/$2^{{2i}}$ being at most 1/log³Δ.","supporting_citations":[],"review_version":1}