{"id":"9e4dfc52-4ac2-497d-83db-1b31e5e790ff","arxiv_id":"2502.06024","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New classical and quantum sublinear query algorithms for (Δ+1)- and (1+ε)Δ-vertex-coloring, with the quantum results breaking the classical Ω(n^{3/2}) query lower bound.","lead":"The paper presents faster algorithms for coloring graphs that have limited connections, including quantum versions that ask fewer questions than classical ones. It matters because quantum search can beat a known limit for this basic graph problem.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 9's coupon-collector bound is inverted and Algorithm 4 repeats 0 times when k=1, so degree-1 vertices never find same-part neighbors and Theorem 5 is false as stated.","rationale":"The reader's verdict CONDITIONAL is well-founded. The quantum (Δ+1)-coloring proof (Theorem 3) is coherent: replacing the classical scan by Grover search and applying Jensen is standard, and the O(n^{3/2} log n /√Δ) bound follows from the same permutation argument as Theorem 1. For Theorem 5, however, the printed Lemma 9 cannot support the conclusion. The threshold in Lemma 9 is dimensionally wrong: it should grow like (k/p) log k, not 1/(pk) log k. The algorithm's repeat count has the correct order for k>1, but it collapses to zero when k=1, which occurs for every degree-1 vertex. Since the theorem quantifies over all graphs of maximum degree Δ, a star is a legitimate counterexample; the algorithm fails with constant probability. This is not merely a missing condition like t≥1; it is a failure of the stated algorithm on a simple input. The fix is small—use max(1, 8(k+1) log(k+1) · log n/log log n) and correct the lemma—so the central algorithmic idea (partition, Grover-coupon-collector, per-part palettes) remains plausible. I therefore keep CONDITIONAL rather than REJECT, but the required revisions are mandatory, not stylistic. The reader's weakest assumption identified Lemma 8's t integrality/range issue, which is real but easily patched; the k=1 zero-repeat issue here produces actual invalid colorings and is more directly tied to the claimed theorem.","tokens_in":10563,"tokens_out":15695,"duration_ms":162019,"concrete_test":"Recompute Lemma 9 for k=1: after t Grover attempts, the single coupon is unseen with probability (1-p)^t, so to get failure ≤ 1/(4n) requires t=Ω(log n), contradicting the printed threshold C/(p k) log k = 0. Alternatively, simulate Algorithm 4 on a star with n=10^3, Δ=999, ε=0.1, partitioning randomly and processing vertices in a fixed order; when a leaf and the center land in the same part and the leaf is processed after the center, the leaf performs zero Grover searches and picks its color from an empty Ni(v). Repeating 10^4 times will produce improper colorings, demonstrating Theorem 5's failure probability bound is not met.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The most load-bearing weakness is the coupon-collector analysis that supports Theorem 5. Lemma 9 states Pr[T ≥ C/(p k) log k] ≤ k^{-C+1}; the threshold is missing a factor of k^2 (the correct tail bound is Pr[T ≥ (Ck/p) log k] ≤ k^{-C+1}, with an additive term for k=1). Because Algorithm 4's outer loop runs 8k log k · log n/log log n times, every degree-1 vertex has k = min((1+ε)Δ/t, d(v)) = 1 and therefore gets exactly 0 Grover searches. Such a vertex never learns its unique neighbor in the same part. Concretely, take a star with center c and n-1 leaves, Δ=n-1, and choose any ε with t = ε²Δ/(6 log n) ≥ 1. For each leaf whose center falls in the same part, if the leaf is colored after the center, the leaf's Ni(v) is empty and the algorithm may assign the center's color; the expected number of such conflicts is Θ(1), not ≤ 1/3. Hence the claimed success probability 2/3 and the query bound O(ε^{-2} n log² n √Δ) fail as stated. The proof of Theorem 5 invokes Lemma 9 with C = 2 log n / log log n, so the incorrect lemma is load-bearing, not a cosmetic typo.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript studies randomized and quantum sublinear query algorithms for vertex coloring. Its three main results are: (i) a Las Vegas (Δ+1)-coloring algorithm using O(n² log n/Δ) adjacency queries in expectation, which combined with greedy coloring gives O(n^{3/2}√log n); (ii) a quantum adjacency-query version using O(n^{3/2} log n/√Δ) expected queries, giving O~(n^{4/3}) when combined with greedy; and (iii) a quantum neighborhood-query algorithm for (1+ε)Δ-coloring that randomly partitions the vertices and uses Grover search plus a coupon-collector analysis to find same-part neighbors, claiming O(ε^{-2} n log² n √Δ) queries and, when combined with (ii), O~(ε^{-1} n^{5/4}). The classical and first quantum results appear sound, but the neighborhood-query algorithm has significant technical errors in its current form.","tokens_in":10791,"tokens_out":17625,"duration_ms":174713,"significance":"If the main results were established, they would constitute clear progress: the classical algorithm improves the expected query complexity of Assadi, Chen, and Khanna by a log factor; the quantum (Δ+1)-coloring bound breaks the classical Ω(n^{3/2}) lower bound; and the (1+ε)Δ-coloring algorithm is the first to use Grover search to accelerate the search for same-part neighbors in the neighborhood-query model. The paper is also refreshingly explicit about the algorithmic ideas, and the proof skeleton is mostly standard concentration and coupon-collector arguments. However, because Theorem 5 rests on an incorrect tail bound and an edge-case bug in the loop count, the claimed improvements in the neighborhood-query setting are not currently supported.","major_comments":[{"comment":"The tail bound in Lemma 9 is inverted and does not follow from its proof. Union bounding over the k coupons gives Pr[some coupon unseen after t trials] ≤ k(1-p/k)^t ≤ k exp(-pt/k). Substituting the lemma's threshold t=C/(pk) log k gives k exp(-C log k / k^2), which is not k^{-C+1} and can be close to k for large k. The correct threshold is t=O((k/p) log k). Theorem 5's proof invokes this lemma with p=1/4, k=(1+ε)Δ/t, and C=2 log n/log log n to conclude that 8k log k·log n/log log n Grover searches fail to find all same-part neighbors with probability at most 1/(4n); since the lemma's threshold is wrong by a factor of k^2, this failure bound is not established. Additionally, Lemma 9 assumes C is a constant, but the application uses C=2 log n/log log n; for k=O(1) the claimed tail bound is too weak to yield the needed 1/(4n) failure probability.","section":"§3.2, Lemma 9 and proof of Theorem 5"},{"comment":"Algorithm 4 performs zero Grover searches whenever k=1. Since k=min((1+ε)Δ/t, d(v)), every degree-1 vertex has k=1, and the outer repeat loop runs 8·1·log 1·...=0 times. Such a vertex never learns whether its unique neighbor lies in the same part. Concretely, for a star with center c and n-1 leaves, Δ=n-1 and t=ε²Δ/(6 log n); for constant ε, about n/t leaves share c's part, and a leaf processed after c has probability Θ(ε²/log n) of choosing c's color, yielding a constant expected number of monochromatic edges. Thus the success probability of Theorem 5 cannot be at least 2/3 as stated. The same loop count is undefined for isolated vertices (d(v)=0, k=0), and the algorithm should treat d(v)=0 separately.","section":"§3.2, Algorithm 4 and Theorem 5"},{"comment":"Lemma 8 requires t=ε²Δ/(6 log n) to be an integer at least 1, but no such hypothesis appears in Lemma 8, Theorem 5, or Corollary 6. For Δ < 6 log n/ε² no partition into t parts exists. This is not merely cosmetic: in Corollary 6 the crossover between Theorem 3 and Theorem 5 occurs at Δ=Θ(ε² n^{1/2}/log n), so Theorem 5 is invoked for small Δ where t may be smaller than 1. The combined O~(ε^{-1} n^{5/4}) bound therefore is not proved for all graphs unless a separate argument covers the small-Δ regime, and the theorem statements must be amended accordingly.","section":"§3.2, Lemma 8 and Corollary 6"}],"minor_comments":[{"comment":"In the pseudocode, after the inner for loop breaks on discovering an edge, control still reaches 'Assign color c to v_{σ(t)}', which would create a monochromatic edge. The intended behavior, namely choosing a new color, is described in the text and used in the proof, so the pseudocode should be corrected.","section":"§2, Algorithm 1"},{"comment":"The phrase 'break choose a new color' is not valid pseudocode; it should say 'continue with a new color' or otherwise make clear that the while loop proceeds to a fresh color choice.","section":"§3.1, Algorithm 2"},{"comment":"Theorem 3 states that the algorithm 'properly colors' but does not specify a success probability. Since Grover and BBHT are bounded-error primitives, the statement should either assume an error-free version of Theorem 7 or include a success probability and a boosting argument.","section":"§3.1, Theorem 3"},{"comment":"The random partition samples without replacement, so di(v) is hypergeometric rather than binomial; the proof should cite the hypergeometric Chernoff bound. The claimed bound is standard and likely correct, but the written justification is incomplete.","section":"§3.2, Lemma 8"}],"recommendation":"major_revision","confidential_remarks":"The manuscript contains a promising approach, and the classical and first quantum results seem sound. However, Theorem 5 is false as stated because of the inverted coupon-collector threshold and the k=1 loop-count bug; these issues appear fixable, so I recommend major revision rather than rejection. Please ask the authors to correct Lemma 9, handle the k=1 and d(v)=0 cases explicitly, and state the required parameter conditions for t."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. The classical (Δ+1)-coloring algorithm (Theorem 1) and the quantum (Δ+1)-coloring algorithm (Theorem 3) are correct and worth having. The quantum (1+ε)Δ-coloring algorithm (Theorem 5) is not correct as stated, and the main new neighborhood-query result should not be relied on until the analysis is fixed.\n\nThe classical result is a clean Las Vegas improvement over Assadi-Chen-Khanna, from O(n^2 log^2 n/Δ) to O(n^2 log n/Δ) expected adjacency queries. The random permutation and hypergeometric generating function argument check out. The paper honestly discloses that Assadi independently proved the same bound, so the community novelty is limited, but the derivation is still a nice teaching example. Theorem 3 similarly checks out: Grover's algorithm accelerates the same-part search, the Jensen step is valid, and the combined Õ(n^{4/3}) bound for (Δ+1)-coloring is new.\n\nThe problems are in Section 3.2. Lemma 9's coupon-collector tail bound is inverted. The correct threshold for T, the time to collect all k coupons with success probability p per step, is C k / p · log k, not C/(p k) · log k. As printed, setting t = C/(p k) log k gives no concentration at all; the union bound is about k, not k^{-C+1}. This is not cosmetic: the proof of Theorem 5 sets C = 2 log n / log log n and uses the lemma to bound the number of Grover searches. The printed bound is off by a factor of k^2.\n\nThere is a second, concrete bug. Algorithm 4 repeats 8k log k · log n / log log n times, which is zero when k = 1. For any degree-1 vertex, k = 1, so the algorithm never searches for a same-part neighbor. In a star, leaves in the same part as the center can then be colored after the center and, with probability about 1/((1+ε)Δ/t), pick the center's color. The expected number of such conflicts is Θ(1), not ≤1/3, so the claimed 2/3 success probability fails. Lemma 8 also silently requires t ≥ 1 and an integer t, but that is a minor fix compared to the breakdown of Lemma 9.\n\nBottom line: the classical and quantum (Δ+1) results are genuinely useful, and the paper is written honestly. But the advertised polynomial improvement for (1+ε)Δ-coloring via quantum neighborhood queries is not established. A serious referee should be able to identify the correct coupon-collector bound and see whether the algorithm can be patched, but as submitted, Theorem 5 is false as stated. I would send it to peer review because the sound parts deserve an outlet, but the decision should be major revision at best, likely reject in current form.","headline":"The classical and (Δ+1)-quantum results are clean and worth knowing, but the (1+ε)Δ quantum neighborhood-coloring theorem is false as stated — Lemma 9's coupon-collector bound is inverted and degree-1 vertices get zero searches.","tokens_in":11421,"tokens_out":4451,"would_cite":true,"duration_ms":39310,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","68Q25","05C15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Random partitions plus quantum search color graphs in Õ(n^{5/4}) queries with (1+ε)Δ colors.","keywords":["vertex coloring","sublinear algorithms","quantum query complexity","adjacency queries","neighborhood queries","random partition","unstructured search","graph algorithms"],"falsifier":"Run the quantum neighborhood-coloring algorithm on random Δ-regular graphs with Δ near 6 log n/ε² and check whether any vertex has more than (1+ε)Δ/t same-part neighbors after the random partition; alternatively, instrument the algorithm to count neighborhood queries and compare the total to O($ε^{{-2}}$ n log² n √Δ). Finding a constant fraction of vertices violating the concentration bound, or query counts growing faster than the claimed bound, would refute the central claim.","tokens_in":10316,"feed_emoji":"🎨","tokens_out":6807,"duration_ms":60155,"temperature":0.7,"pith_summary":"The paper proposes three randomized sublinear query algorithms for vertex coloring, with the goal of coloring a graph of maximum degree Δ faster than reading all edges. Its central claim is that random assignment of colors, checked against already-colored neighbors, yields a (Δ+1)-coloring in O(n² log n/Δ) adjacency queries in expectation, which drops to O($n^{{3/2}}$√log n) when combined with the greedy algorithm. If quantum adjacency queries are allowed, the color-conflict check can be replaced by an unstructured search that finds a conflicting neighbor in square-root time, giving Õ($n^{{4/3}}$) queries for (Δ+1)-coloring and breaking the classical Ω($n^{{3/2}}$) query lower bound. A second quantum algorithm partitions vertices randomly, uses quantum search to collect each vertex's same-part neighbors, and colors each part from its own palette in (1+ε)Δ colors using O($ε^{{-2}}$ n log² n √Δ) neighborhood queries; combined with the first quantum algorithm, this yields Õ($ε^{{-1}}$ $n^{{5/4}}$) queries. If correct, the paper replaces the dense-graph coloring bottleneck with a randomized partition plus a quantum search primitive.","feed_headline":"Quantum search breaks classical query bound for graph coloring","feed_subtitle":"Random partitions plus quantum search yield a (1+ε)Δ-coloring in ~n^{5/4} queries.","key_machinery":"The mechanism is a random equitable partition of the vertex set into t = ε²Δ/(6 log n) parts, coupled with the quantum search primitive for finding marked items in an unsorted list. Lemma 8 guarantees that, with probability at least 1−1/n, every vertex has at most (1+ε)Δ/t neighbors inside its own part, so each part can be colored greedily from a private palette of that size. To collect the same-part neighbors of a vertex v, the algorithm prepares a uniform superposition over the indices 1,...,d(v) of v's neighborhood list and repeatedly applies reflections that mark indices whose neighbors lie in the same part; each successful run returns one such index uniformly at random, and a coupon-collector argument bounds the number of runs needed to find all of them. Constructing the part-membership reflection requires no graph queries, so the only query cost is the O(√Δ) per search plus the repetitions.","core_discovery":"Stated on the paper's own terms: the (Δ+1)-coloring problem in the adjacency-query model has a Las Vegas algorithm whose expected query count is O(n² log n/Δ), improving the prior Monte Carlo bound by a log n factor; when the greedy algorithm (nΔ neighborhood queries) is used for small Δ, the combined colorer runs in O($n^{{3/2}}$√log n) expected queries. With quantum adjacency queries, the same random-order scheme colors with O($n^{{3/2}}$ log n/√Δ) queries in expectation, yielding Õ($n^{{4/3}}$) overall. The paper's third result is a quantum neighborhood-query algorithm that properly colors with (1+ε)Δ colors in O($ε^{{-2}}$ n log² n √Δ) queries, succeeds with probability at least 2/3, and, when combined with the quantum adjacency algorithm, colors in Õ($ε^{{-1}}$ $n^{{5/4}}$) queries. The conceptual discovery is that quantum search can find a vertex's same-part neighbors without scanning its full neighborhood list, turning the classical greedy scan into a square-root-accelerated coupon collection.","pith_inferences":["The paper's concentration argument needs t ≥ 1, meaning Δ on the order of log n/ε²; for graphs of smaller maximum degree the algorithm as stated does not apply, and a combined algorithm would need to switch to a different regime.","A natural extension is to replace the random partition by a pseudorandom or deterministic partition with similar concentration; if such a partition can be built without too many queries, the log n factors in t may shrink.","The success probability of 2/3 in the neighborhood-query algorithm can presumably be amplified to 1−1/poly(n) by repetition, at a cost of a log n factor, which the authors do not spell out.","The same quantum-accelerated coupon collection may improve other sublinear graph problems, such as finding all neighbors in a vertex subset or list-coloring, whenever the relevant subset is sparse."],"forward_implications":["A (Δ+1)-coloring can be found in O(n^{3/2}√log n) expected queries classically, matching the known Ω(n^{3/2}) lower bound up to a √log n factor.","Quantum adjacency queries allow (Δ+1)-coloring in Õ(n^{4/3}) queries, breaking the classical Ω(n^{3/2}) query lower bound.","With (1+ε)Δ colors, quantum neighborhood queries give an Õ(ε^{-1} n^{5/4})-query coloring algorithm, a polynomial improvement over the previous best (1+ε)Δ-coloring bound.","The random-partition plus quantum-search recipe applies to any setting where a vertex's relevant neighbors form an unknown subset of its neighborhood list; it replaces ordered scanning by square-root search and coupon collection.","The Las Vegas result can be boosted to Monte Carlo success probability 1−1/poly(n) at the cost of a log n factor, matching the earlier high-probability bound."],"supporting_citations":[{"why":"Supplies the prior (Δ+1)-coloring algorithm and the Ω(n^{3/2}) query lower bound that the classical algorithm improves and the quantum algorithm beats.","marker":"[2]"},{"why":"Introduces the random-color framework for (1+ε)Δ-coloring and the query-count combination strategy that both classical and quantum algorithms extend.","marker":"[11]"},{"why":"Gives the quantum search algorithm for an unknown number of marked items, the subroutine used to find same-part neighbors and accelerate conflict checking.","marker":"[4]"},{"why":"Establishes the square-root speedup for database search, the quantum primitive on which the adjacency-query speedup relies.","marker":"[7]"}],"fun_headline_variants":["Quantum search speeds up graph coloring queries","Quantum queries color graphs faster than classical","Square-root speedup for graph coloring with quantum search","Improved sublinear coloring via quantum adjacency queries","Quantum algorithm trims query count for graph coloring"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Lemma 8's concentration bound: a random equitable partition keeps every vertex's same-part degree at most (1+ε)Δ/t with high probability, which silently requires Δ to be large enough, roughly Δ ≳ log n/ε²; if that fails, a vertex can have more same-part neighbors than its part's palette, and the greedy-in-parts coloring runs out of colors.","fun_headline_variants_meta":{"raw":{"variants":["Quantum search speeds up graph coloring queries","Quantum queries color graphs faster than classical","Square-root speedup for graph coloring with quantum search","Improved sublinear coloring via quantum adjacency queries","Quantum algorithm trims query count for graph coloring"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000504,"raw_usage":{"total_tokens":2464,"prompt_tokens":950,"completion_tokens":1514,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":566,"completion_tokens_details":{"reasoning_tokens":1447}},"tokens_in":566,"tokens_out":1514,"duration_ms":11562,"temperature":1.0,"reasoning_tokens":1447,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T17:01:55.013050+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the quantum neighborhood-coloring algorithm on random Δ-regular graphs with Δ near 6 log n/ε² and check whether any vertex has more than (1+ε)Δ/t same-part neighbors after the random partition; alternatively, instrument the algorithm to count neighborhood queries and compare the total to O($ε^{{-2}}$ n log² n √Δ). Finding a constant fraction of vertices violating the concentration bound, or query counts growing faster than the claimed bound, would refute the central claim.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the square-root speedup for database search, the quantum primitive on which the adjacency-query speedup relies."},{"cited_title":"Assadi, Y","cited_arxiv_id":null,"evidence_quote":"Supplies the prior (Δ+1)-coloring algorithm and the Ω(n^{3/2}) query lower bound that the classical algorithm improves and the quantum algorithm beats."},{"cited_title":"Boyer, G","cited_arxiv_id":null,"evidence_quote":"Gives the quantum search algorithm for an unknown number of marked items, the subroutine used to find same-part neighbors and accelerate conflict checking."}],"review_version":1}