{"id":"d8678c92-2481-4741-af87-b60da196ed05","arxiv_id":"2608.08296","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A maximal independent set and a (deg+1)-coloring of any graph can be computed deterministically in O(n+m) work and polylog depth, matching the sequential greedy bound.","lead":"This paper gives deterministic parallel algorithms that solve graph coloring and maximal independent set using only linear total work and polylogarithmic depth. It settles a long-standing open question in parallel computing, where every previous deterministic method did superlinear total work.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The coloring theorem depends on an unproved adaptation of Luby's deterministic coloring algorithm to arbitrary sorted palettes, asserted without proof in Corollary 5.3; if that adaptation fails, Theorem 1.2 loses its subroutine.","rationale":"The reader's weakest_assumption and my independent read converge on the same point: Corollary 5.3's reliance on an unproved property of Luby's coloring algorithm. I checked the surrounding machinery and found the benefit-problem algorithm (Theorem 3.1), the involution-based balancing argument (Lemma 4.1), and the bootstrapping theorem (5.1) internally consistent; the dummy vertex for odd n is handled by the degree bound, and the partitioning and extension charges are accounted for. The coloring reduction is the only place where a nonstandard subroutine is invoked without justification. The claim is not contradicted anywhere in the paper; it is simply asserted. Since the paper gives no formal verification and no code, a reader cannot check it from the text. This is exactly the kind of missing support that should keep a strong claim conditional: if the Luby adaptation holds, the coloring result follows; if it fails, Theorem 1.2 is unsupported while the MIS result (Corollary 5.2) survives. My recommendation therefore leaves the reader's CONDITIONAL verdict unchanged.","tokens_in":12313,"tokens_out":13876,"duration_ms":133874,"concrete_test":"Obtain [Lub93] and trace its deterministic (Δ+1)-coloring algorithm with each vertex's palette replaced by an arbitrary sorted set C(v) of size deg(v)+1. Check whether the correctness proof—especially the benefit function and the conditional-expectation step—uses only the size and sortedness of C(v), or whether it relies on all vertices sharing the global palette {1,...,Δ+1}. As a minimal instance, test the algorithm on a path v1-v2-v3 with palettes {1,2}, {1,3}, {2,3}: a proper list coloring exists, so if the derandomization rejects a vertex solely because its palette is not the common {1,2,3}, the Corollary 5.3 assertion is false. If the proof goes through verbatim with per-vertex sorted palettes, the concern is resolved and Theorem 1.2 stands.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step for Theorem 1.2 is the unproved assertion at the end of Corollary 5.3: '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.' Theorem 5.1's hypothesis (B) requires a deterministic subroutine for the residual instances that arise after the extension step, and those instances are list-coloring instances with arbitrary sorted palettes—the first piece has uniform palettes, but later pieces have palettes from which colors used by earlier neighbors were removed. No proof, lemma, or citation to a specific part of [Lub93] is supplied for this adaptation. If the assertion is false, there is no subroutine to plug into Theorem 5.1 for coloring: the O(m) total work argument depends on each piece of the sparse partition being solvable in O(m_i polylog n), and the piece instances are not ordinary (Δ+1)-coloring instances. The MIS corollary (5.2) does not depend on this assertion and appears sound. Because the rest of the coloring reduction is fully specified, this single unverified property is the critical soft spot.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12470,"tokens_out":20816,"duration_ms":201489,"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":[{"comment":"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.","section":"Corollary 5.3, final paragraph"},{"comment":"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.","section":"Corollary 5.3, palette update"}],"minor_comments":[{"comment":"Typo: \"amound\" should be \"amount\".","section":"Section 1, paragraph on [GG25]"},{"comment":"Typo: \"Luby's algortihm\" should be \"Luby's algorithm\".","section":"Section 5, before Theorem 5.1"},{"comment":"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.","section":"Corollary 5.3, truncation sentence"},{"comment":"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.","section":"Lemma 4.1, benefit instance construction"},{"comment":"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.","section":"Theorem 4.2, statement"}],"recommendation":"major_revision","confidential_remarks":"This is a strong and important paper if the coloring gaps can be closed. The missing proof or citation for the list-coloring version of Luby's algorithm is the critical risk; the palette-update range assumption is a separate but fixable issue. The MIS result and the partition/benefit machinery appear sound. I recommend major revision rather than rejection because both concerns are local and plausibly repairable within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat'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.\n\nThe 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.\n\nMinor 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.\n\nWho 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.","headline":"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.","tokens_in":13109,"tokens_out":9794,"would_cite":false,"duration_ms":90201,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Deterministic parallel algorithms for MIS and $(\\deg+1)$-coloring run in $O(n+m)$ work and polylogarithmic depth, matching the sequential greedy bound.","keywords":["parallel algorithms","work-depth model","maximal independent set","graph coloring","derandomization","pairwise independence","sparse graph partition","deterministic algorithms"],"falsifier":"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.","tokens_in":11991,"feed_emoji":"🧩","tokens_out":11132,"duration_ms":103857,"temperature":0.7,"pith_summary":"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.","feed_headline":"MIS and graph coloring now run in linear work, polylog depth","feed_subtitle":"The paper removes the last polylog overhead, matching the sequential greedy bound on parallel work.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the pairwise-independence derandomization framework (bit-pair benefit problem) and the deterministic coloring and MIS algorithms used as subroutines in Section 5.","marker":"[Lub93]"},{"why":"Provides the linear-work refinement of Luby's benefit problem that Section 3 adapts to the degree-balancing constraints.","marker":"[Han95]"},{"why":"Gives the previous best deterministic MIS work bound, $O((n+m)\\mathrm{poly}(\\log\\log n))$, whose overhead Theorem 1.1 removes.","marker":"[GG25]"},{"why":"Gives the previous best deterministic $(\\Delta+1)$-coloring bound, $O((n+m)\\log^2 n)$, which Theorem 1.2 improves to linear.","marker":"[Han96]"},{"why":"One of the poly-log-overhead deterministic MIS algorithms that Corollary 5.2 uses as the subroutine on partition pieces.","marker":"[GS89b]"},{"why":"Parallel merge sort is used in the degree sort and stable integer sort that keep the partitioning and benefit computations linear.","marker":"[Col88]"},{"why":"Defines the work-depth model and the prefix-sum and filtering primitives on which all complexity bounds are stated.","marker":"[J\\'aJ92]"}],"fun_headline_variants":["Deterministic parallel coloring and MIS achieve optimal work","Linear work, polylog depth for deterministic coloring and MIS","Parallel algorithms match greedy work for coloring and MIS","Optimal work parallel deterministic coloring and MIS now possible","MIS and (Δ+1)-coloring solved in linear work, polylog depth"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Deterministic parallel coloring and MIS achieve optimal work","Linear work, polylog depth for deterministic coloring and MIS","Parallel algorithms match greedy work for coloring and MIS","Optimal work parallel deterministic coloring and MIS now possible","MIS and (Δ+1)-coloring solved in linear work, polylog depth"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001009,"raw_usage":{"total_tokens":4196,"prompt_tokens":807,"completion_tokens":3389,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":423,"completion_tokens_details":{"reasoning_tokens":3303}},"tokens_in":423,"tokens_out":3389,"duration_ms":23779,"temperature":1.0,"reasoning_tokens":3303,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T00:14:48.391802+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}