{"id":"eb781dfa-ee53-4810-8eff-e0daa321e296","arxiv_id":"2607.27159","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"Graph k-coloring admits a randomized one-sided-error algorithm in O((2−ε_k)^n) time for every fixed k, breaking the classical 2^n barrier.","lead":"For every fixed number of colors k, graph k-coloring can be solved in randomized time O((2−ε_k)^n) for some ε_k>0. This removes the long-standing 2^n barrier that held for all k≥7.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly flags the black-box use of Zamir’s (α,Δ)-bounded list-coloring algorithm as the most external premise, yet that premise is applied only inside its stated regime (fixed k, fixed α=½, fixed Δ=d(k)). The paper’s novel pieces—trimmed-convolution queries (Lem 4.1), the branching routine with two base cases (Lem 4.2), and the sampling/averaging argument (Lem 4.3 + lines 8–24 of the algorithm)—are written out in full and close under the chosen parameters. Because the case split is exhaustive once those parameters are fixed, and because an independent concurrent proof of the same theorem exists, no single internal step appears load-bearing enough to move the verdict. The suggested concrete test simply forces the parameter arithmetic for the smallest unsettled k into the open; a pass leaves the ACCEPT verdict intact.","tokens_in":13053,"tokens_out":594,"duration_ms":11434,"concrete_test":"Fix k=7. Instantiate the concrete constants of Thm 4.4 (η, ζ, T, c=kT, d=max{T(k−1)+1,d(k,c)}, λ) and recompute the three bases appearing at the end of Lem 4.2 and in the sampling stage of Thm 4.4 (H(1/2−η), 1−μ/2, 1−λ/2, and 1+σ log k+(ζ−1)|A|/n). Verify each is strictly less than 1; if any fails, the claimed ε_7 collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Thm 1.2 / Thm 4.4) is supported by a complete, self-contained case analysis. The three branches (many low-degree vertices via Thm 3.2; many η-good palettes via the branching of Lem 4.2; sampling + averaging via Lem 4.3 + Thm 4.1) exhaust the witness colorings once d and T are fixed as functions of k. The external primitive Thm 3.2 is used only for constant α=1/2 and constant Δ=d(k), which is exactly the regime [Zam21] states; the paper’s own parameters (η=1/(6(k−1)), ζ, T, λ, d) are chosen so that every exponential base is strictly less than 2. Concurrent independent confirmation by Zamir [Zam26] further lowers uniqueness risk without introducing a new correctness gap. Ordinary constant-level arithmetic slips remain possible in a long parameter-heavy proof, but none is load-bearing under a good-faith reading.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper proves that for every fixed k ≥ 3 there exists ε_k > 0 such that Graph k-Coloring on n-vertex graphs can be solved by a randomized one-sided-error algorithm in time O((2-ε_k)^n). The algorithm works with a fixed color-class profile p and combines three regimes: (i) many low-degree vertices, handled by Zamir’s (α,Δ)-bounded list-coloring primitive; (ii) many vertices whose witness neighborhoods are concentrated on η-good palettes, handled by a branching procedure that feeds restricted list instances into a trimmed-subset-convolution oracle (Lemma 4.1); (iii) many vertices seeing a heavy palette, handled by random sampling of a small set S, brute-force coloring of S, and an averaging argument (Lemma 4.3) that produces a usable list constraint for the same oracle. Parameters (η, T, d, λ, σ, ζ, …) are chosen as explicit functions of k so that every exponential base is strictly less than 2. The result removes the 2^n barrier of Björklund–Husfeldt–Koivisto for all k, matching an independent concurrent proof of Zamir.","tokens_in":13290,"tokens_out":1001,"duration_ms":50040,"significance":"The 2^n poly(n) bound for k-coloring had stood since 2009; exponential improvements were previously known only for k ≤ 6 and for structured degree regimes. Establishing a uniform (2-ε_k)^n algorithm for every fixed k is a clean and long-sought advance in exact exponential algorithms. The proof is fully constructive, re-uses standard black-box primitives (trimmed Möbius inversion and Zamir’s bounded-degree list coloring) in a transparent case analysis, and supplies explicit (if tower-like) parameter settings that make the exponential savings rigorous. Concurrent independent confirmation by Zamir further supports correctness without diminishing the contribution of the distinct technical route taken here.","major_comments":[],"minor_comments":[{"comment":"The parameter cascade in the proof of Theorem 4.4 (especially the concrete lower bound on T and the definition of d via Lemma 4.2) is correct but extremely dense. A short “parameter summary” table or a one-paragraph roadmap listing the inequalities that each constant is required to satisfy would make verification substantially easier.","section":"Theorem 4.4 / Parameters"},{"comment":"In Lemma 4.1 the |R|=2 case sketches a bipartite-component DP in a footnote. Expanding the DP to a short inline paragraph (or citing a standard reference for exact 2-coloring with prescribed part sizes) would remove any ambiguity about polynomial-time solvability of that subproblem.","section":"Lemma 4.1"},{"comment":"Several numerical thresholds (15/16, 99/100, 2^{-k-5}, 6k, …) appear without a single place that records why each constant is safe. Collecting them once, with the elementary inequalities they rely on, would help the reader track the probability and mass calculations in the case analysis.","section":"Section 4"},{"comment":"Minor typesetting: accented characters and math operators are occasionally broken (e.g., “na ¨ ıvely”, “Bj¨ orklund”). A pass through the LaTeX source would clean these up.","section":"Throughout"},{"comment":"The pseudocode block inside Theorem 4.4 mixes algorithmic steps with analysis remarks. Separating a clean algorithm listing from the surrounding correctness argument would improve readability.","section":"Theorem 4.4"}],"recommendation":"accept","confidential_remarks":"The concurrent independent manuscript of Zamir (arXiv:2607.25973) proves the same theorem by a different route and was posted slightly earlier. The present paper properly acknowledges that work and offers a genuinely distinct proof; I see no priority or novelty obstacle to acceptance. The heavy but fully disclosed use of an LLM for drafting does not affect the mathematical content."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The one thing to know: Pratt closes the long-open gap that fixed-k graph coloring is in randomized O((2−ε_k)^n) for every k, not just k≤6 or structured graphs. That matches the shape we already have for k-SAT. Concurrent Zamir work gets the same theorem another way, so uniqueness is gone, but the result is real.\n\nWhat is new is the case split on witness colorings. After peeling off the many-low-degree case with Zamir’s (α,Δ) list-coloring black box, the remaining high-degree vertices are partitioned by the palettes they “see” at least T times. Either most mass sits on η-good (light) palettes, handled by a branching routine that grows restricted sets W_R and falls back to list coloring or the trimmed-convolution primitive, or some heavy palette U_R0 is large; then random sampling of a small S plus an averaging lemma produces a usable list restriction on a linear-size set A, and Theorem 4.1 finishes in 2^{n−|A|} time. The parameters (η=1/(6(k−1)), T, ζ, λ, d) are chosen by hand so every base is strictly below 2. The write-up is constructive and the citations are standard (BHK09, BHKK08, Zamir 2021/23).\n\nSoft spots are ordinary for this genre, not load-bearing. The proof is long and parameter-heavy; a constant-level slip is possible though none jumped out on a careful read. Everything rests on Zamir’s structured list-coloring for constant α and Δ=d(k), which is exactly the regime that paper claims. ε_k is existential and tiny. AI assistance is disclosed for repairing one base case of the branching lemma; the author says he verified everything. None of that sinks the argument.\n\nThis is for people who care about exact exponential algorithms and fine-grained CSP runtimes. A serious referee should see it. I would cite it when the 2^n barrier for coloring comes up, and I would bring the high-level case split to reading group even if we skip the constant-chasing.","headline":"Clean qualitative win: fixed-k coloring finally beats 2^n for every k, with a readable case-split proof and independent concurrent confirmation.","tokens_in":14027,"tokens_out":553,"would_cite":true,"duration_ms":14046,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","05C15","68R10"],"pacs":[],"model":"grok-4.5","headline":"For every fixed number of colors k, graph k-coloring can be decided in time O((2-ε_k)^n) by a one-sided randomized algorithm.","keywords":["graph coloring","exact algorithms","exponential time","subset convolution","list coloring","trimmed Möbius inversion","profile coloring"],"falsifier":"Implement the full algorithm for a concrete small k (say k=7) with the stated parameter settings, run it on a family of n-vertex graphs known to be 7-colorable, and check whether the measured running time is consistently o(2^n) while the acceptance probability on yes-instances stays bounded away from zero.","tokens_in":13829,"feed_emoji":"▷","tokens_out":1124,"duration_ms":17771,"temperature":0.7,"pith_summary":"Graph k-coloring is a classic NP-complete problem. The long-standing general algorithm of Björklund, Husfeldt and Koivisto runs in O*(2^n) time for any k. Exponential improvements below 2^n were previously known only for k ≤ 6 and for graphs with special structure. This paper shows that the 2^n barrier can be broken for every fixed k: there is a positive ε_k (depending only on k) and a randomized algorithm with one-sided error that decides k-colorability in O((2-ε_k)^n) time. The result places coloring in the same qualitative regime as k-SAT and other parameterized CSPs, where fixing the parameter already yields a strict exponential improvement over the unbounded case. A concurrent independent proof of the same statement exists; the two approaches differ in technique.","feed_headline":"k-coloring drops below 2^n for every fixed k","feed_subtitle":"A one-sided randomized algorithm decides k-colorability in O((2-ε_k)^n) time, ending the 2^n barrier for k≥7","key_machinery":"A list-coloring primitive (Theorem 4.1) that, after O*(2^{H(1/2-η)n}) preprocessing via trimmed subset convolution, answers queries “does there exist a profile-p coloring in which a given set A receives colors from a palette R?” in time O*(2^{n-|A|}) whenever R is η-good or |R| ≤ 2. The main algorithm routes every witness coloring into one of three cases (many low-degree vertices, many vertices whose neighborhoods are almost η-good, or many vertices that see a heavy non-good palette) and reduces each case to this primitive or to an existing bounded-degree list-coloring routine.","core_discovery":"For every fixed integer k ❥ 3 there exists ε_k > 0 such that Graph k-coloring admits a randomized one-sided-error algorithm running in time O((2-ε_k)^n). The algorithm always rejects non-k-colorable graphs and accepts k-colorable graphs with probability at least 2/3. The same statement holds when the target color-class sizes (the profile) are fixed in advance.","pith_inferences":["The same case-split-plus-restriction idea may transfer to other fixed-arity CSPs whose natural 2^n algorithms rely on subset convolution or inclusion-exclusion.","Because ε_k tends to zero with k, the result does not yet yield a uniform (2-ε)^n algorithm for chromatic number; closing that gap is a natural next target.","Quantitative optimization of the many parameters (T, η, λ, d, …) could produce the first explicit numerical bases below 2 for k=7,8,…."],"forward_implications":["For every fixed k the exponential base of exact k-coloring is strictly smaller than 2.","The same base improvement holds when color-class sizes are prescribed in advance.","Only graphs that are simultaneously dense, highly irregular, and free of large almost-good palettes remain candidates for a true 2^n lower bound under standard algorithmic techniques.","The trimmed-convolution / list-restriction template becomes a reusable primitive for other partition problems indexed by a fixed number of parts."],"fun_headline_variants":["k-coloring finally breaks 2^n for every fixed k","Randomized one-sided algorithm beats 2^n on k-coloring","Graph k-coloring in O((2-ε_k)^n) for all k","Every k now has ε_k > 0 beating the 2^n coloring barrier","Fixed-k coloring admits (2-ε)^n randomized time"],"cache_read_input_tokens":128,"weakest_assumption_plain":"The argument treats as a black box an earlier algorithm that already solves k-list-coloring exponentially faster than 2^n on graphs that contain a constant fraction of bounded-degree vertices; if that subroutine fails for the concrete degree bounds used here, the claimed savings disappear in two of the three cases.","fun_headline_variants_meta":{"raw":{"variants":["k-coloring finally breaks 2^n for every fixed k","Randomized one-sided algorithm beats 2^n on k-coloring","Graph k-coloring in O((2-ε_k)^n) for all k","Every k now has ε_k > 0 beating the 2^n coloring barrier","Fixed-k coloring admits (2-ε)^n randomized time"]},"model":"grok-4.5","effort":"low","cost_usd":0.003476,"raw_usage":{"total_tokens":1073,"prompt_tokens":686,"num_sources_used":0,"completion_tokens":108,"cost_in_usd_ticks":34764000,"prompt_tokens_details":{"text_tokens":686,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":279,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":686,"tokens_out":108,"duration_ms":5579,"temperature":1.0,"reasoning_tokens":279,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-30T10:40:36.327000+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Implement the full algorithm for a concrete small k (say k=7) with the stated parameter settings, run it on a family of n-vertex graphs known to be 7-colorable, and check whether the measured running time is consistently o(2^n) while the acceptance probability on yes-instances stays bounded away from zero.","supporting_citations":[],"review_version":1}