Improved Sublinear Algorithms for Classical and Quantum Graph Coloring

Asaf Ferber; Liam Hardiman; Xiaonan Chen

REVIEW 3 major objections 4 minor 1 cited by

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring

T0 review · 3 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Random partitions plus quantum search color graphs in Õ(n^{5/4}) queries with (1+ε)Δ colors.

desk verdict 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. read the letter →

arxiv 2502.06024 v1 pith:PDUCDEML submitted 2025-02-09 cs.DS

Asaf Ferber , Liam Hardiman , Xiaonan Chen This is my paper · ORCID

classification cs.DS MSC 68Q1268Q2505C15

keywords vertexcoloringsublinearalgorithmsquantumquerycomplexityadjacencyqueriesneighborhoodrandompartitionunstructuredsearchgraph

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

The 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.

There 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.

Bottom 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.

Referee Report

3 major / 4 minor

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.

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 (3)

[§3.2, Lemma 9 and proof of Theorem 5] 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.
[§3.2, Algorithm 4 and Theorem 5] 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.
[§3.2, Lemma 8 and Corollary 6] 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.

minor comments (4)

[§2, Algorithm 1] 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.
[§3.1, Algorithm 2] 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.
[§3.1, Theorem 3] 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.
[§3.2, Lemma 8] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: every claimed complexity is reduced to external benchmarks and in-paper probabilistic bounds, with no fitted parameters or self-citation chains.

full rationale

The paper's derivations are self-contained reductions to external results. Theorem 1 is proved directly from a randomized permutation argument with a Chernoff/hypergeometric-style tail bound derived in the proof; it does not assume the target runtime. Theorem 3 applies Grover/BBHT search as an external oracle-speedup primitive and reuses the already-proved classical argument, which is legitimate complexity composition, not circularity. Theorem 5 reduces to a random-partition concentration bound (Lemma 8) and a coupon-collector tail bound (Lemma 9), both stated and proved inside the paper from first principles; no parameter is fitted to the claimed output, and the success probability is obtained by a union bound over these in-paper events. Corollaries 2, 4, and 6 are obtained by balancing two independently proved query bounds, which is standard minimization, not a self-referential prediction. The citations to Assadi-Chen-Khanna, Morris-Song, Grover, and Boyer-Brassard-Hoyer-Tapp are all external benchmarks or established algorithms; none is by the present authors, and none smuggles in the theorem being proved. The manuscript's apparent defects, such as the suspicious constant in Lemma 9's coupon-collector tail bound and the degenerate k=1 case in Algorithm 4, are correctness concerns about the proof, not circularity: even a wrong bound is not an input-to-output equivalence. Consequently, no circular step can be exhibited from the text, and the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper rests on standard mathematical tools (Chernoff, hypergeometric identities, Grover/BBHT search, coupon collector). No parameters are fitted to data and no entities are invented. The only non-black-box assumptions are the concentration of random equitable partitions and the correctness of the BBHT search theorem, both external to the paper's original contribution.

assumptions (4)

standard math Greedy coloring uses Δ+1 colors and O(nΔ) neighborhood queries.
Used as the neighborhood-query baseline g(Δ) in Corollary 2, Corollary 4, and Corollary 6; introduced in Section 1.
standard math Chernoff bound: for a random equitable partition, intra-part degrees concentrate, giving Lemma 8.
Invoked in Section 3.2 to guarantee each induced subgraph has max degree at most (1+ε)Δ/t; the paper does not prove negative correlation but the bound is standard.
standard math BBHT quantum search (Theorem 7): finds a uniformly random marked item in O(sqrt(N/k)) queries if k>0 and certifies k=0 in O(sqrt(N)) queries.
Used as a black box in Theorems 3 and 5; the paper states it as Theorem 7 and does not reprove it.
standard math Coupon-collector tail bound (Lemma 9, corrected threshold t = C k log k / p).
Used to bound the number of Grover searches needed to recover all same-part neighbors of a vertex; the printed lemma has a typo in the threshold.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Improved Sublinear Algorithms for Classical and Quantum Graph Coloring." pith.science (2026). https://pith.science/paper/PDUCDEML

@misc{pith2026250206024,
  author       = {Pith},
  title        = {Pith review of: Improved Sublinear Algorithms for Classical and Quantum Graph Coloring},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PDUCDEML}},
  note         = {Machine review of arXiv:2502.06024}
}

abstract

We present three sublinear randomized algorithms for vertex-coloring of graphs with maximum degree $\Delta$. The first is a simple algorithm that extends the idea of Morris and Song to color graphs with maximum degree $\Delta$ using $\Delta+1$ colors. Combined with the greedy algorithm, it achieves an expected runtime of $O(n^{3/2}\sqrt{\log n})$ in the query model, improving on Assadi, Chen, and Khanna's algorithm by a $\sqrt{\log n}$ factor in expectation. When we allow quantum queries to the graph, we can accelerate the first algorithm using Grover's famous algorithm, resulting in a runtime of $\tilde{O}(n^{4/3})$ quantum queries. Finally, we introduce a quantum algorithm for $(1+\epsilon)\Delta$-coloring, achieving $O(\epsilon^{-1}n^{5/4}\log^{3/2}n)$ quantum queries, offering a polynomial improvement over the previous best bound by Morris and Song.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Graph k-Coloring in Average Sublinear Time
cs.DS 2026-07 conditional novelty 8.0 of 10

The exact average-case complexity of k-coloring random k-colorable graphs is Θ(nk) for every k ≤ n^{1/37}.

Reference graph

Works this paper leans on

12 extracted references · 11 canonical work pages · cited by 1 Pith paper

[1]

Alon and S

N. Alon and S. Assadi. Palette Sparsiﬁcation Beyond (∆+1 ) Vertex Coloring. Approxi- mation, Randomization, and Combinatorial Optimization. Al gorithms and Techniques (AP- PROX/RANDOM), 176:6:1–6:22, 2020

work page 2020
[2]

Assadi, Y

S. Assadi, Y. Chen, and S. Khanna. Sublinear Algorithms f or (∆ + 1) Vertex Coloring. Pro- ceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Alg orithms (SODA) , pages 767–786, 2019

work page 2019
[3]

Beame, P

P. Beame, P. Koutris, and D. Suciu. Communication steps f or parallel query processing. J. ACM, 64(6), oct 2017

work page 2017
[4]

Boyer, G

M. Boyer, G. Brassard, P. Høyer, and A. Tapp. Tight bounds on quantum searching. Fortschritte der Physik: Progress of Physics , 46(4-5):493–505, 1998

work page 1998
[5]

Chang, M

Y.-J. Chang, M. Fischer, M. Ghaﬀari, J. Uitto, and Y. Zheng . The Complexity of (∆ + 1) Color- ing in Congested Clique, Massively Parallel Computation, a nd Centralized Local Computation. Proceedings of the 2019 ACM Symposium on Principles of Distri buted Computing, 2018

work page 2019
[6]

Goldreich

O. Goldreich. Introduction to Property Testing . Cambridge University Press, 2017. 12

work page 2017
[7]

L. K. Grover. A fast quantum mechanical algorithm for dat abase search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing , STOC ’96, page 212–219, New York, NY, USA, 1996. Association for Computing Machiner y

work page 1996
[8]

L. K. Grover. Quantum computers can search rapidly by usi ng almost any transformation. Phys. Rev. Lett., 80:4329–4332, May 1998

work page 1998

Show all 12 references

[9]

R. M. Karp. Reducibility Among Combinatorial Problems . Springer US, 1972

1972
[10]

N. D. Mermin. Quantum Computer Science: An Introduction . Cambridge University Press, 2007

2007
[11]

Morris and F

J. Morris and F. Song. Simple vertex coloring algorithm s. arXiv:2102.07089v1 [cs.DS] , 2021

2021 arXiv
[12]

M. Parter. (∆ + 1) Coloring in the Congested Clique Model . In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) , volume 107 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 160:1–160:14, 2018. 13

2018

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.

[1] [1]

Alon and S

N. Alon and S. Assadi. Palette Sparsiﬁcation Beyond (∆+1 ) Vertex Coloring. Approxi- mation, Randomization, and Combinatorial Optimization. Al gorithms and Techniques (AP- PROX/RANDOM), 176:6:1–6:22, 2020

work page 2020

[2] [2]

Assadi, Y

S. Assadi, Y. Chen, and S. Khanna. Sublinear Algorithms f or (∆ + 1) Vertex Coloring. Pro- ceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Alg orithms (SODA) , pages 767–786, 2019

work page 2019

[3] [3]

Beame, P

P. Beame, P. Koutris, and D. Suciu. Communication steps f or parallel query processing. J. ACM, 64(6), oct 2017

work page 2017

[4] [4]

Boyer, G

M. Boyer, G. Brassard, P. Høyer, and A. Tapp. Tight bounds on quantum searching. Fortschritte der Physik: Progress of Physics , 46(4-5):493–505, 1998

work page 1998

[5] [5]

Chang, M

Y.-J. Chang, M. Fischer, M. Ghaﬀari, J. Uitto, and Y. Zheng . The Complexity of (∆ + 1) Color- ing in Congested Clique, Massively Parallel Computation, a nd Centralized Local Computation. Proceedings of the 2019 ACM Symposium on Principles of Distri buted Computing, 2018

work page 2019

[6] [6]

Goldreich

O. Goldreich. Introduction to Property Testing . Cambridge University Press, 2017. 12

work page 2017

[7] [7]

L. K. Grover. A fast quantum mechanical algorithm for dat abase search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing , STOC ’96, page 212–219, New York, NY, USA, 1996. Association for Computing Machiner y

work page 1996

[8] [8]

L. K. Grover. Quantum computers can search rapidly by usi ng almost any transformation. Phys. Rev. Lett., 80:4329–4332, May 1998

work page 1998