{"id":"fb5f4b57-84ad-4578-978c-59f4a0bb5a03","arxiv_id":"2607.26592","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"The exact average-case complexity of k-coloring random k-colorable graphs is Θ(nk) for every k ≤ n^{1/37}.","lead":"For random k-colorable graphs, this paper proves that finding a proper k-coloring takes Θ(nk) time on average — linear in n for constant k, and therefore far less than reading the entire graph. If correct, it settles a 30-year open question in average-case complexity and supplies a local algorithm that answers individual color queries with only poly(k) probes.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Phase 2's O(k) sample budget is insufficient: collecting all-but-one color classes is a coupon-collector problem requiring Θ(k log k) samples, so the O(nk) proof fails for nonconstant k.","rationale":"The paper's central claim is that average-case k-coloring has complexity Θ(nk) for k ≤ n^{1/37}. The reader's weakest assumption was the unique-colorability certificate (Lemma 4.4) and its arithmetic slip. That is a real issue but it is a constant-factor repair: the actual core size ν = Θ(k^9 log k) can be chosen larger than 160000 k^5 with a sufficiently large constant. A more load-bearing problem is the sampling phase: the algorithm as written does not achieve O(k) samples per vertex because finding neighbors in all but one color class is exactly a coupon-collector process, which requires Θ(k log k) samples in expectation. For k growing as a power of n, the fixed 200k budget fails with probability tending to 1, so the claimed O(nk) average runtime is not proven. This is not an objection to the existence of an O(nk) algorithm—a simple permutation-based sampling variant would repair it—but it is a substantive gap in the submitted proof. The reader's verdict of CONDITIONAL remains appropriate because both problems are fixable without changing the paper's main ideas, but the specific flaw I would flag is different from the reader's. I therefore disagree with the reader's choice of weakest assumption and recommend the manuscript be revised to correct the sampling analysis (and the Lemma 4.4 constant) before acceptance.","tokens_in":34502,"tokens_out":52526,"duration_ms":492884,"concrete_test":"Derive the success probability of Algorithm 2's sampling loop for a random dense k-partite graph: for r = Ck samples, the probability a fixed color class is never successfully hit is about e^{-C/2}; the probability all k−1 other classes are hit is roughly (1 − e^{-C/2})^{k−1} ≈ exp(−k e^{−C/2}). For any fixed constant C, this tends to 0 as k → ∞. Evaluate at C=200 and k = n^{1/37} (e.g., k = 10^{50}): the claimed 0.99 success probability fails catastrophically. This directly tests whether Claim 5.1's 'expected samples at most 200k' can hold.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Algorithm 2 (Local-Good-Core-Neighbors), each vertex is given only r = 200k samples, and each sample picks a color uniformly from COLORS, then a vertex in that core color class. For a vertex to be colored, it must discover a neighbor in every color class except its own. With edge probability 1/2 per sampled vertex, the number of samples needed to hit k−1 distinct colors is the coupon collector time: the expected value is (k/2) H_k ≈ k log k, not O(k). Claim 5.1 asserts 'the expected number of samples required to find connections to all but one D_j is at most 200k', which ignores the coupon-collector cost. For k > e^{100}, 200k is below the mean, and the probability of success for a single vertex decays as approximately exp(−k e^{−100}) → 0. Since the theorem allows k up to n^{1/37}, k can be arbitrarily large as n grows; Phase 2 would then fail on almost all vertices, and Phase 3's global budget of 100nk samples is likewise too small to compensate. Thus the claimed Θ(nk) average runtime is not established by the algorithm as written. The issue is repairable by sampling colors in a random permutation and spending O(1) expected samples per wrong color, but that modification is not in the manuscript. (A separate but secondary issue is the arithmetic slip in Lemma 4.4: Lemma 3.5 requires s > 160000 k^5, not 204 k^5.)","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the average-case time complexity of k-coloring a graph drawn uniformly from all labeled k-colorable n-vertex graphs. It claims a tight bound: for every k ≤ n^{1/37}, the average runtime is Θ(nk), which for constant k is linear in n and therefore sublinear in the Θ(n^2) input size. The main algorithmic idea is to sample a small 'core' subgraph of size poly(k), color it with Kučera's algorithm, certify its unique colorability through local degree/codegree statistics that imply ε-regularity, and then propagate the core coloring to the rest of the graph in two sampling phases; a brute-force phase handles the rare graphs that are not 'okay'. A deterministic version is claimed with eO(nk) average runtime, and an Ω(nk) lower bound is proved for every algorithm that is correct on all k-colorable graphs. The paper also claims a local computation algorithm (LCA) with poly(k) average probe complexity. The proof structure is explicit and the main claims are precise.","tokens_in":34906,"tokens_out":26879,"duration_ms":271843,"significance":"If the result holds, it is a major advance: it breaks the long-standing quadratic barrier for average-case k-coloring with constant k, resolves the exact average-case complexity up to constant factors for a broad range of k, and introduces a new certification technique—using degree and codegree statistics as a poly(k)-size certificate of unique colorability. The lower bound is simple but apparently correct, and the upper-bound algorithm is worst-case correct, not just correct on most inputs. The paper relies on standard external theorems (Dyer–Frieze, Kučera, Alon–Duke–Lefmann–Rödl–Yuster, Björklund–Husfeldt–Koivisto) rather than on fitting parameters to the target; the algorithmic architecture is original and the claims are falsifiable. However, the proof as written contains several numerical inconsistencies in the core-certification lemma and in the concentration calculations that support the core size; these need to be repaired before the main theorem can be accepted.","major_comments":[{"comment":"The proof applies Lemma 3.5 and states that its hypothesis s > (20k^{5/4})^4 is satisfied because s ≥ c0 k^5 with c0 = 204. But (20k^{5/4})^4 = 160000 k^5, not 204 k^5. Thus, as written, Definition 4.1 does not imply the condition needed for Lemma 3.5. This is load-bearing because Lemma 4.4 is exactly the certificate that makes the algorithm worst-case correct: an uncertified core could be colored in multiple ways and propagate an invalid coloring. The fix is local—take c0 ≥ 160000, or use the actual core size ν = Θ(k^9 log k), which dominates k^5 for large k—but the false implication must be corrected.","section":"Section 4.2, Lemma 4.4 and Definition 4.1"},{"comment":"The proof of degree regularity states that concentration holds for ν ≥ c k^2 log(k)/ε^8 with ε = 1/(10k), which is ν ≥ c k^{10} log k. But Definition 4.2 fixes ν = Θ(k^9 log k). A direct Chernoff bound for Bin(ν/k, 1/2) with relative error ε^4 requires δ^2 μ = ε^8 · ν/(2k) ≥ Ω(log k), i.e., ν ≥ Ω(k^9 log k), not k^{10} log k. The written inequality is off by a factor of k and is inconsistent with the stated ν. This is load-bearing for the claim that many subgraphs of size ν are good cores; it needs to be corrected in the same revision.","section":"Section 4.3, Lemma 4.6"},{"comment":"The proof of Claim 5.1 states that the expected number of samples needed by Local-Good-Core-Neighbors is at most 200k and then asserts that the vertex is placed into S_i with probability 0.99. An expectation bound does not imply a 0.99 success probability; a Markov bound gives only P(T ≤ 200k) ≥ 1/2. The waiting time is a sum of geometric random variables, and a tail bound is needed. This is not the coupon-collector-with-replacement issue that a reviewer might worry about: Algorithm 2 removes a color from COLORS on success, so every success is on a previously uncollected color and the expected time is indeed O(k). Nevertheless, the claimed high probability requires a concentration argument, and the constant 200 may need to be enlarged for small k. Without this, the claim that each inner loop succeeds with probability 1/2 on awesome graphs is not established.","section":"Section 5.2, Claim 5.1"}],"minor_comments":[{"comment":"The displayed lower bound for the edge density d̄ is hard to parse; the factors involving (1+1/(100k)) and (1−ε^4) should be written more carefully and rederived.","section":"Section 4.2, Lemma 4.4"},{"comment":"The inline name 'Kucera1995' should be typeset consistently as 'Kučera 1995' or 'Kučera's algorithm'.","section":"Throughout"},{"comment":"In the second part of the proof, the role of V_B relative to D and S should be clarified: presumably V_B is disjoint from the selected samples, but this is not stated explicitly.","section":"Section 4.3, Lemma 4.8"},{"comment":"The global iteration counter 'Repeated' is incremented by the per-vertex iteration count, but the relationship between this global budget and the per-vertex success probability is not explained. A short remark would help.","section":"Section 5.1, Algorithm 7"}],"recommendation":"major_revision","confidential_remarks":"The technical issues are concentrated in the numerical constants of the certification lemma and in a missing tail bound in Claim 5.1; both appear repairable without changing the algorithmic architecture. The stress-test coupon-collector objection does not land, because Algorithm 2 shrinks COLORS after each successful discovery, so the expected time is O(k), not O(k log k). I recommend major revision rather than rejection: the authors should correct the c0 = 204 arithmetic, align the ν thresholds in Lemma 4.6 with Definition 4.2, and supply the missing concentration proof. After those repairs, the constant-k result, which is the headline contribution, is likely sound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Take a look at this one before the next meeting. The paper claims to settle the average-case complexity of k-coloring: Θ(nk) over uniformly random k-colorable graphs for k ≤ n^{1/37}, breaking a quadratic barrier that has stood since Dyer-Frieze. That claim is genuinely new and, for constant k, I believe it. The upper bound is a clever combination of a uniquely-colorable core, certified via degree/codegree regularity, and a two-phase propagation trick; the lower bound is a clean adversary argument. The paper also gives an LCA with poly(k) probe complexity and a derandomization. These are real contributions, and the writing is clear.\n\nBut there are two problems. The first is small and easily fixed: Lemma 4.4 says (20k^{5/4})^4 = 204k^5, but it's 160000k^5, so the constant c0=204 in Definition 4.1 is wrong. Since the actual core size is Θ(k^9 log k), this doesn't break the architecture, but the lemma as stated needs correction.\n\nThe second is more serious and affects the proof of the O(nk) bound for non-constant k. Phase 2's Local-Good-Core-Neighbors gives each vertex only 200k samples, drawn by picking a color uniformly from the remaining colors. To eliminate all but one color, a vertex must collect at least k-1 distinct colors — a coupon collector problem that takes ~2k ln k samples in expectation, not O(k). The proof of Claim 5.1 asserts the expected number is at most 200k, which is wrong for k larger than about e^100. Since the theorem allows k up to n^{1/37}, k can be arbitrarily large, and then Phase 2 would fail on almost every vertex; Phase 3 can't rescue it because the S_i sets it relies on were supposed to come out of Phase 2. The good news is the fix is simple: iterate through a random permutation of colors and spend O(1) expected samples per color, which makes Phase 2 work in O(k) time and restores the Θ(nk) claim. But as written, the algorithm and its analysis are inconsistent for the full range of k.\n\nFor constant k — which is the setting the abstract emphasizes — the coupon-collector constant is hidden and the result stands. So the main message survives. The paper needs a revision before I'd trust the non-constant-k theorem, but the ideas are solid and the lower bound is unaffected.\n\nThis deserves serious peer review. Send it.","headline":"Strong paper on average-case k-coloring, but the O(nk) proof has a real coupon-collector flaw for non-constant k; fixable, and the constant-k result survives.","tokens_in":35436,"tokens_out":5657,"would_cite":true,"duration_ms":47998,"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":"The paper claims that the average-case complexity of k-coloring is Θ(nk) for k ≤ n^{1/37} — linear in n and sublinear in the Θ(n²) input — with matching upper and lower bounds.","keywords":["average-case complexity","graph k-coloring","sublinear algorithms","random graphs","graph regularity","local computation algorithms","unique colorability","worst-case correctness"],"falsifier":"Compute, for random planted k-partite graphs, the probability that a subgraph of size 204k^5 satisfies the degree/codegree certificate of Definition 4.1 while having more than one proper k-coloring. For k=3, brute-force search over random such subgraphs will settle whether the certificate is sufficient at that size; the paper's intended repair uses the much larger core ν=Θ(k^9 log k), so the check should be repeated at that size.","tokens_in":34395,"feed_emoji":"🎨","tokens_out":11137,"duration_ms":97814,"temperature":0.7,"pith_summary":"This paper aims to settle the average-case time complexity of graph k-coloring on uniformly random k-colorable graphs. It claims that for k up to n^{1/37}, the exact average complexity is Θ(nk): linear in the number of vertices and hence sublinear in the Θ(n²) input size. The paper gives a randomized algorithm achieving O(nk) average time, a deterministic version running in Õ(nk), and a lower bound showing every worst-case-correct algorithm needs Ω(nk) time on average. If true, this closes a three-decade gap and shows the quadratic input-size barrier is not inherent to the average case. The approach also yields a local computation algorithm for k-coloring with poly(k) probes per color query.","feed_headline":"Average k-coloring runs in Θ(nk), breaking the quadratic barrier","feed_subtitle":"Constant-k coloring is linear in n, hence sublinear in the Θ(n²) input, with a matching lower bound.","key_machinery":"The good core: a random subgraph of size ν = Θ(k^9 log k) whose color classes are balanced and whose degree and codegree statistics approximately match a random k-partite graph. These statistics certify unique colorability via the graph regularity lemma (they imply ε-regularity between color classes, which forbids a second coloring). Propagation is done by inferring a vertex's color from adjacencies to all but one color class of the core, then repeating with the newly colored vertices. The lower bound uses a counting argument over queried entries of the adjacency matrix.","core_discovery":"The central claim is that the average-case complexity of k-coloring is Θ(nk) for every k ≤ n^{1/37}, over the uniform distribution on labeled k-colorable graphs. The upper bound comes from an algorithm that first samples a small 'core' of size poly(k) and certifies that this core has a unique proper k-coloring, using only degree and codegree statistics that imply graph regularity and therefore rule out any second coloring. Once the core is certified, the algorithm propagates its coloring to the rest of the graph in two sampling phases, coloring vertices whose color is forced by adjacencies to already-colored sets; the rare graphs that resist both phases are handled by brute force, whose e^{O","pith_inferences":["The certificate step as written contains a constant error: Lemma 4.4 requires core size above (20k^{5/4})^4 = 160000k^5, while Definition 4.1 only guarantees 204k^5; the paper's later choice ν=Θ(k^9 log k) would repair this, so the argument is likely fixable but not as stated.","The core-certification idea could generalize to other average-case NP-hard problems on dense random instances: find a small subgraph whose solution is forced by local statistics, then propagate; the paper leaves this as an explicit open direction.","A practical test: implement the two-phase sampling on random planted k-colorable graphs with k=3 or 4 and n in the thousands; the query count should scale ~ nk, not n², and the certificate should accept a random core with overwhelming probability.","The lower bound holds even in the adjacency-list access model and against randomized algorithms, since an adversary can fix the random string, so the Θ(nk) complexity is not an artifact of the matrix model."],"forward_implications":["For constant k, the average runtime of k-coloring becomes linear in n, so the problem becomes sublinear in the Θ(n²) adjacency-matrix input.","The Ω(nk) lower bound shows the O(nk) randomized algorithm and the Õ(nk) deterministic algorithm are optimal up to polylog factors, and no worst-case-correct algorithm can do better on average.","The algorithm is worst-case correct: if the fast phases fail, it runs an exhaustive search, but that happens with probability exponentially small in n, keeping the average runtime Θ(nk).","The local computation algorithm answers a color query for any vertex using poly(k) probes on average, which is far beyond the reach of worst-case LCAs, where even 2-coloring can require probing an edge that connects two large components."],"fun_headline_variants":["Average k-coloring complexity is Θ(nk), optimal","Quadratic barrier broken: k-coloring in Θ(nk) average","Sublinear average-time k-coloring for constant k","Optimal Θ(nk) average-time algorithm for k-coloring","k-coloring average case: exact Θ(nk) complexity"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The argument's load-bearing premise is that a poly(k)-vertex random subgraph's degree and codegree statistics certify unique colorability, but the written constants are inconsistent — the proof needs core size above 160,000·k^5 while the definition only claims 204·k^5 — so the certificate as stated is not yet proven; the paper's larger core size of Θ(k^9 log k) is intended to absorb this.","fun_headline_variants_meta":{"raw":{"variants":["Average k-coloring complexity is Θ(nk), optimal","Quadratic barrier broken: k-coloring in Θ(nk) average","Sublinear average-time k-coloring for constant k","Optimal Θ(nk) average-time algorithm for k-coloring","k-coloring average case: exact Θ(nk) complexity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000543,"raw_usage":{"total_tokens":2540,"prompt_tokens":949,"completion_tokens":1591,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":693,"completion_tokens_details":{"reasoning_tokens":1505}},"tokens_in":693,"tokens_out":1591,"duration_ms":11122,"temperature":1.0,"reasoning_tokens":1505,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T12:43:56.327905+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute, for random planted k-partite graphs, the probability that a subgraph of size 204k^5 satisfies the degree/codegree certificate of Definition 4.1 while having more than one proper k-coloring. For k=3, brute-force search over random such subgraphs will settle whether the certificate is sufficient at that size; the paper's intended repair uses the much larger core ν=Θ(k^9 log k), so the check should be repeated at that size.","supporting_citations":[],"review_version":1}