{"id":"2e342c28-2036-4136-8dbe-edcac1eaeb49","arxiv_id":"2607.25973","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":9.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every fixed k-coloring problem has a randomized algorithm running in (2−ε_k)^n time, beating the 2^n bound for chromatic number.","lead":"This paper proves that for every fixed number of colors k, deciding whether an n-vertex graph is k-colorable has a randomized algorithm running in (2−ε)^n time for some ε>0, strictly beating the general 2^n algorithm that computes the chromatic number. It resolves a long-standing open problem in exact exponential-time algorithms and introduces an iterable list-coloring reduction technique.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Bootstrap depends on unverified two-block black box (Thm 3.7); if it has hidden conditions, the sub-2^n claim collapses.","rationale":"After careful reading, the proof of the new bootstrap appears internally coherent: the seed-shortening lemma, the progress invariant for |A_Q| and |B_R|, the success-probability induction, and the running-time bookkeeping all check out. The main theorem genuinely reduces to two external black boxes: the bounded-degree solver (Theorem 3.5) and the two-block restricted-coloring theorem (Theorem 3.7). The former is older and less central; the latter is the single point where the entire sub-2^n gain is achieved at the terminal step. If Theorem 3.7 is false or has hidden hypotheses, no amount of internal correctness can save the main claim. The paper cites the theorem as a combination of lemmas from [Zam23] but does not reproduce them, making it impossible for a reader to verify from this manuscript alone. This is a legitimate soft spot, but not a discovered flaw. I therefore agree with the reader's identification and recommend no change to the verdict, while urging independent verification of Theorem 3.7.","tokens_in":28649,"tokens_out":23885,"duration_ms":204937,"concrete_test":"Independently re-derive Corollary 3.8 from first principles: write out the inclusion-exclusion / Extensions-Sum derivation for the special case V_c={v:c∈L(v)}, A={v:L(v)⊆Q}, B={v:L(v)⊆R}, without invoking Theorem 3.7. Verify that the running time is O*(2^{n-|A|}+2^{n-|B|}) and note any additional hypotheses needed (e.g., the palette partition Q,R must be fixed and disjoint, which holds here). If the derivation succeeds, the concern is resolved; if it requires conditions not stated in Theorem 3.7, the bootstrap's terminal step is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 5.2) is proved by iterating the general bootstrap (Theorem 5.1). Each bootstrap step creates two linear supported sets A_Q and B_R, and then invokes Corollary 3.8 to decide list colorability in O*(2^{n-|A_Q|}+2^{n-|B_R|}) time. Corollary 3.8 is a one-line consequence of Theorem 3.7, the two-block restricted-coloring black box imported from [Zam23]. The paper does not reproduce the proof of Theorem 3.7; it only cites Lemmas 3.11, 3.14, 3.16 and Observation 3.23 from [Zam23]. This is the least secure link in the chain: if Theorem 3.7 has a hidden condition (e.g., the domains V_c must arise from a container family, or the partition Q∪R must satisfy some size/balance constraint, or the time bound requires additional preconditions), then Corollary 3.8 would not apply as stated, and the terminal two-block call could be as slow as 2^n. Unlike other steps, this is not a minor technicality: the whole purpose of the two-block machinery is to provide the sub-2^n stitching of the Q-side and R-side, and no alternative argument is given. The same black box is also used in [Zam23] for regular graphs, so a subtle mismatch with the present list-coloring setting could go unnoticed. Thus the correctness of the main theorem is exactly as secure as Theorem 3.7.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that for every fixed k, k-coloring on n-vertex graphs admits a randomized algorithm with running time (2−ε_k)^n, and more generally that list-coloring over a fixed palette of size K admits such an algorithm. The proof establishes a bootstrap: from a sub-2^n algorithm for (k−1)-list-coloring over a fixed palette P, it constructs one for k-list-coloring over P. A warm-up handles one new gap by producing many vertices with lists of size two and applying a new deterministic interpolation algorithm (Theorem 4.4); the general bootstrap (Theorem 5.1) produces two large sets of vertices whose lists are supported on complementary subpalettes and combines them using a two-block restricted-coloring black box (Corollary 3.8). Iterating from polynomial-time 2-list-coloring yields Theorem 5.2. Section 4.4 gives an ETH-based lower bound showing that the interpolation parameter cannot be improved to q=1 with a palette-independent constant. Section 6 provides an informal quantitative estimate of the saving.","tokens_in":29007,"tokens_out":24841,"duration_ms":229817,"significance":"Should the result be correct, it resolves a long-standing gap: for every fixed k, k-coloring is strictly easier than the O*(2^n) algorithm for chromatic number, matching the qualitative situation for k-SAT. The paper is largely self-contained beyond two cited black boxes; it includes pseudocode for the reductions, explicit constants, a deterministic interpolation algorithm, and a conditional lower bound. The main theorem has a clear falsifiable consequence—an algorithm for every fixed k with an improved base—and the paper identifies concrete open problems, including palette-independent list coloring and quantitative improvements to ε_k. The proof's new machinery (seed shortening, pair-complement bootstrap, two supported sets) is substantial. The main risk is the reliance on the imported two-block theorem.","major_comments":[{"comment":"The entire general bootstrap depends on the two-block restricted-coloring black box. The manuscript gives a one-paragraph indication that Theorem 3.7 follows from Lemmas 3.11, 3.14, 3.16 and Observation 3.23 of [Zam23], but does not reproduce the argument or state the exact theorem in [Zam23] with its hypotheses. Corollary 3.8 then plugs arbitrary list domains into this theorem. Since the terminal call of Theorem 5.1 is the only place where the two linear supported sets A_Q and B_R are combined, and no alternative combination argument is provided, the main theorem is exactly as secure as this imported theorem. Please include a complete proof of Theorem 3.7, or a precise statement of the corresponding theorem/lemmas in [Zam23] with a step-by-step derivation of the O*(2^{|D_Q|}+2^{|D_R|}) bound, and confirm that no hidden conditions on the domains V_c or the partition Q∪R are needed. This","section":"§3.6, Theorem 3.7/Corollary 3.8; used in §5.1"},{"comment":"The proof of Theorem 5.1 introduces the constant Ntr = ceil(2n/p0^m) for the number of independent trials. It is correct that p0^{-m} ≤ 2^{λdn} and that the total running-time exponents are κ+λd, 1−d+λd, and 1−γ+λd. However, the argument is compressed and the reader must reconstruct how the failure probability e^{-n} follows from a success probability of at least (1/2)p0^m per trial while only the favorable Q is guaranteed to have this property. I verified the calculation, but I recommend making the role of the favorable Q and the union over Q explicit in the text, since this is load-bearing for the claimed sub-2^n time bound.","section":"§5.1, Theorem 5.1"}],"minor_comments":[{"comment":"The appendix states that an AI model 'reproduced (or copied)' the proof of [BHKK07] and displayed 'severe lack of attribution.' The final manuscript does cite [BHKK07] in Lemma 3.3, so I do not treat this as a technical defect. However, the wording should be reconciled with the paper's attribution practices and with the journal's AI-use policy.","section":"Appendix A"},{"comment":"Section 6 is explicitly informal and not needed for the main theorems. If Proposition 6.1 is meant to be a formal statement, it should be labeled as such and proved with the constants tracked; if it is only a heuristic estimate, the informal status should be stated at the start of the section, not only in the surrounding prose.","section":"Section 6"},{"comment":"The pseudocode uses the phrase 'if EasySolver-E(I) finds a coloring then return YES.' The easy solver is sometimes described as a decision algorithm; the decision-to-search conversion of Lemma 3.1 is invoked in the main text but not explicitly in the pseudocode. Aligning the pseudocode with Lemma 3.1 would avoid ambiguity.","section":"Algorithms 1 and 3"}],"recommendation":"major_revision","confidential_remarks":"The technical content is strong and the main theorem is important. My recommendation is driven by the unverified dependency on Theorem 3.7; I would like to see the derivation made fully checkable before publication. The unusual Appendix A is worth an editorial look for AI-use policy compliance, but it does not affect my technical assessment."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline is correct: this resolves the long-standing gap where only k ≤ 6 had sub-2^n coloring algorithms. The paper gives a coherent iterable reduction from (k−1)-list-coloring to k-list-coloring over a fixed palette, bootstrapped from polynomial-time 2-SAT, and it is honest about what it does not do. The binary-list interpolation theorem is a clean stand-alone result, and the ETH-based lower bound showing q>1 is a nice counterweight. Section 6's explicit tower-type bound for ε_k is refreshingly candid; it tells the reader exactly how non-constructive the existence proof is, while still establishing existence. All of this is real work, not a sketch.\n\nThe soft spot is precisely the one the stress-test flags. The general bootstrap's terminal step uses Corollary 3.8, a one-line consequence of Theorem 3.7, the two-block restricted-coloring black box imported from Zamir's STOC 2023 paper. That theorem is not reproved here, and the paper only cites Lemmas 3.11, 3.14, 3.16 and Observation 3.23 from the earlier work. If the published theorem really is as stated—arbitrary allowed domains V_c and time O*(2^{|D_Q|}+2^{|D_R|})—then the chain holds. But the statement as imported is broader than some container-based results, and a subtle missing condition on the domains or the partition would break the general bootstrap. This is not a minor technicality; it is the load-bearing joint. It may well be fine, since the source is peer-reviewed, but a paper this consequential should either reproduce the proof of Theorem 3.7 in an appendix or state explicitly which theorem in Zam23 is being used and why all conditions are met.\n\nI would also flag the AI Storytime appendix, though not as a mathematical flaw. It says the author used an AI model to help complete the interpolation argument and that the model reproduced the BHKK07 proof without attribution in intermediate outputs. The final paper does cite BHKK07, and the author claims the main ideas are his, so the math is not undermined. Still, the appendix is off-topic for a technical paper and invites unnecessary provenance questions. I would advise removing it or moving it to an informal separate note.\n\nNet: the central argument is coherent, the result is important, and the transparency about constants and limitations is good. The paper deserves serious peer review, with the referee instructed to verify the exact statement and proof of the two-block theorem before signing off on the general case.","headline":"The main theorem is genuine and the proof is far more than a sketch, but the general bootstrap leans on the un-reproduced two-block theorem from Zamir's STOC 2023 paper, and that is exactly where a referee should push hard.","tokens_in":29449,"tokens_out":2003,"would_cite":true,"duration_ms":25312,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","68Q25","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every fixed number of colors k, the paper proves that k-coloring an n-vertex graph admits a randomized algorithm running in (2−ε_k)^n time for some positive ε_k, strictly faster than the general 2^n bound for computing the chromatic num","keywords":["graph coloring","list coloring","exponential-time algorithms","fixed palette","bootstrap reduction","randomized algorithms","subset convolution","two-block restrictions"],"falsifier":"A counterexample to the two-block restricted-coloring claim, or a concrete list-coloring instance where a completed bootstrap step violates the invariant that $|A_Q|$ grows by $r$ and $|B_R|$ never drops below $\\gamma n$, would settle the matter. On the lower-bound side, an unconditional proof that some fixed $k$-coloring requires $2^{\\Omega(n)}$ time would refute the theorem.","tokens_in":28553,"feed_emoji":"","tokens_out":4072,"duration_ms":34345,"temperature":0.7,"texified_at":"2026-08-05T21:49:07.823903+00:00","pith_summary":"The paper tries to prove that for every fixed number of colors k, deciding whether an n-vertex graph is k-colorable can be done in $(2 - \\varepsilon_k)^n$ randomized time for some positive $\\varepsilon_k$ — strictly faster than the $2^n$ time needed to compute the chromatic number in general. It achieves this by turning list-coloring itself into a bootstrapping device: from any sub-$2^n$ algorithm for $(k-1)$-list-coloring over a fixed palette, it builds a sub-$2^n$ algorithm for k-list-coloring over the same palette. The significance is that this removes a long-standing gap: previously only $k \\le 6$ had such improvements, while general chromatic-number computation remained the best known for all larger k. If correct, every fixed-size coloring and list-coloring problem over a fixed palette has a strictly better-than-$2^n$ worst-case algorithm, matching the qualitative situation for $k$-SAT.","texify_model":"deepseek-v4-flash","texify_usage":{"total_tokens":8220,"prompt_tokens":826,"completion_tokens":7394,"prompt_tokens_details":{"cached_tokens":0},"prompt_cache_hit_tokens":0,"prompt_cache_miss_tokens":826,"completion_tokens_details":{"reasoning_tokens":6619}},"feed_headline":"k-coloring beats the 2^n barrier for every fixed k","feed_subtitle":"A new bootstrap turns sub-2^n list-coloring algorithms into faster k-coloring algorithms, closing a long-standing gap.","key_machinery":"The central mechanisms are (1) a seed-shortening lemma that, via randomized sampling and enumeration, either finds a coloring or reduces all remaining lists by one color; (2) a pigeonhole argument on the constant-sized complement sets $Q_v = P \\setminus L(v)$, producing two linear-size 'supported' vertex sets $A_Q$ (lists $\\subseteq Q$) and $B_R$ (lists $\\subseteq R$); (3) a two-block restricted-coloring black box (based on the Extensions-Sum machinery) that decides colorability with allowed color domains in $O^*(2^{|D_Q|}+2^{|D_R|})$ time; and (4) a binary-list interpolation algorithm that solves instances with many size-two lists in $O^*(2^{n-b/M})$ time. The bootstrap stitches these together so each step preserves a linear prog","core_discovery":"The central claim is that k-coloring on n-vertex graphs admits a randomized algorithm running in time $(2 - \\varepsilon_k)^n$ for every fixed k, equivalently for list-coloring over a fixed palette of size K. The proof constructs an iterable reduction: assuming a sub-$2^n$ algorithm for $(k-1)$-list-coloring over a fixed palette P, one obtains a sub-$2^n$ algorithm for k-list-coloring over P. The reduction samples small random vertex sets to shorten color lists, pigeonholes the finitely many list-complements to find a linear-size set of vertices sharing the same two-block partition $Q \\cup R$ of the palette, and then uses a two-block restricted-coloring black box to combine colorings on the two supported sets in sub-2^","pith_inferences":["If the open question of a palette-independent q<2 for binary-list interpolation is resolved positively, the fixed-palette restriction could likely be lifted to give sub-2^n algorithms for k-list-coloring with unbounded palettes.","The paper's quantitative estimate that 1/ε_K grows like a tower of height Θ(K) suggests the actual savings are tiny for large K; future work may focus on improving this tower dependence, paralleling the history of k-SAT constants.","The ETH-based lower bound ruling out q=1 for interpolation hints that a fundamental trade-off between list length and palette size may be intrinsic, not an artifact of the proof.","A derandomization of the main randomized algorithm, or a polynomial-space version, would be natural next steps; the current method relies on exponentially small failure probability and exponential space via the two-block black box."],"forward_implications":["Every fixed k now has a randomized sub-2^n k-coloring algorithm, answering a question open for all k>6.","List-coloring over a fixed palette of size K is solvable in (2−ε_K)^n time, which also covers k-coloring with K=k.","As a corollary of the warm-up, 7-coloring gets the first (2−ε)^n algorithm, via the new interpolation theorem for instances with many size-two lists.","The new binary-list interpolation algorithm is a standalone tool: instances with b vertices on lists of size at most two over a fixed palette run in O*(2^{n-b/M}) time.","If the bootstrap is iterated from the polynomial-time 2-list-coloring algorithm, it yields the claimed algorithms for all K; no base-saving assumption beyond the two stated black boxes is needed."],"fun_headline_variants":["k-coloring falls below 2^n time for every fixed k","Sub-2^n k-coloring for every fixed k now proven","All fixed k: k-coloring beats the 2^n wall","k-coloring: faster than 2^n for every fixed k","Every fixed k gets a sub-2^n k-coloring algorithm"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is the correctness of the two-block restricted-coloring black box (Theorem 3.7), which states that colorability with allowed color domains can be decided in $O^*(2^{|D_Q|}+2^{|D_R|})$ time for any partition of the palette; if this theorem has a hidden condition or fails for the supported sets produced by the bootstrap, the whole iterated reduction collapses.","fun_headline_variants_meta":{"raw":{"variants":["k-coloring falls below 2^n time for every fixed k","Sub-2^n k-coloring for every fixed k now proven","All fixed k: k-coloring beats the 2^n wall","k-coloring: faster than 2^n for every fixed k","Every fixed k gets a sub-2^n k-coloring algorithm"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000823,"raw_usage":{"total_tokens":3431,"prompt_tokens":735,"completion_tokens":2696,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":479,"completion_tokens_details":{"reasoning_tokens":2605}},"tokens_in":479,"tokens_out":2696,"duration_ms":16579,"temperature":1.0,"reasoning_tokens":2605,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T00:57:11.237047+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A counterexample to the two-block restricted-coloring claim, or a concrete list-coloring instance where a completed bootstrap step violates the invariant that $|A_Q|$ grows by $r$ and $|B_R|$ never drops below $\\gamma n$, would settle the matter. On the lower-bound side, an unconditional proof that some fixed $k$-coloring requires $2^{\\Omega(n)}$ time would refute the theorem.","supporting_citations":[],"review_version":1}