Pith. sign in

REVIEW 3 major objections 4 minor 58 references

Graph k-Coloring in Average Sublinear Time

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

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

Pith's one-line read 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.

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

arxiv 2607.26592 v1 pith:F46TKG3F submitted 2026-07-29 cs.DS cs.CCmath.CO

Cassandra Marcussen , Edward Pyne , Ronitt Rubinfeld , Asaf Shapira , Shlomo Tauber This is my paper · ORCID
classification cs.DScs.CCmath.CO
keywords average-casecomplexitygraphk-coloringsublinearalgorithmsrandomgraphsregularitylocalcomputationuniquecolorabilityworst-casecorrectness
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

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

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

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [Section 4.2, Lemma 4.4 and Definition 4.1] 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.
  2. [Section 4.3, Lemma 4.6] 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.
  3. [Section 5.2, Claim 5.1] 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.
minor comments (4)
  1. [Section 4.2, Lemma 4.4] 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.
  2. [Throughout] The inline name 'Kucera1995' should be typeset consistently as 'Kučera 1995' or 'Kučera's algorithm'.
  3. [Section 4.3, Lemma 4.8] 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.
  4. [Section 5.1, Algorithm 7] 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.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity; minor self-citations are non-load-bearing.

full rationale

The main derivation is self-contained against external benchmarks. The O(nk) upper bound is obtained by sampling a random core, certifying its unique colorability (Lemma 4.4) using the external ADL+94 degree/codegree-to-regularity lemma, and then transferring a structural theorem from the planted model B_A to the uniform distribution via Dyer-Frieze [DF89]. The edge probability 1/2 is part of the model, not a fitted parameter; no target runtime is used to define the certificate or the structural properties. The self-citations [MPR+25], [MRS25], and [BCM+24] are used for high-level technique comparison, quality-control intuition, and a definition, respectively; they are not black-box inputs to Theorems 1-3, and no uniqueness theorem is imported from the authors' prior work. The Ω(nk) lower bound is an independent adversary/counting argument. Two non-circular correctness gaps should be flagged separately: (i) in Lemma 4.4 (Section 4.2), the arithmetic slip '(20k^{5/4})^4 = 204k^5' (it is 160000k^5) means the certificate size in Definition 4.1 does not satisfy Lemma 3.5 as written, though the later ν=Ω(k^9 log k) can repair it; (ii) in Claim 5.1 (Section 5.2), the assertion that the expected number of samples to hit all-but-one core color class is at most 200k ignores the coupon-collector factor Θ(k log k) for nonconstant k. These affect correctness, not circularity. Hence the circularity score is low, reflecting only the presence of minor, non-load-bearing self-citations.

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

The paper introduces no new physical entities and fits no constants to data. It uses several hand-chosen polynomial-in-k thresholds (core size, σ, B) whose values are only constrained to be large enough; these affect constant factors and the exact exponent range k ≤ n^{1/37}. The central claim rests on external prior theorems, which are cited and not reproven.

free parameters (4)
  • c_ν = unspecified (chosen large enough)
    Scales the core size ν = 2 c_ν k^9 log k used in Definition 4.2 and Algorithm 11. Only affects constant factors, not the Θ(nk) asymptotic.
  • c_0 = 204 in Definition 4.1; should be 160000 = 20^4
    Minimum size of a good core in the unique-colorability certificate. Lemma 4.4 requires |H| > 160000 k^5, but Definition 4.1 states 204 k^5; the paper's own arithmetic conflicts.
  • c_σ = unspecified constant
    Threshold σ = c_σ log k in the definition of awesome graphs. Lemma 4.8 requires σ ≥ c_σ log k for a sufficiently large constant.
  • B_O and σ_O constants = c k log k
    Parameters for 'okay' graphs in Definition 4.5. Chosen so the failure probability in Theorem 8 is at most 3k^{-2n}.
assumptions (6)
  • domain assumption Theorem 5 [DF89]: E_{G∼U}[N_C(G)] ≤ 2 for k ≤ n^{1/2}
    Used to bound the total probability mass ρ_bal of approximately balanced colorings when transferring from planted model to uniform distribution in Section 4.4.
  • domain assumption Theorem 6 [Kučera95]: deterministic O(n^2/k) average coloring for the planted model B_A
    Used as the Kucera1995 subroutine to color the sampled core H in Phase 1 and in the LCA.
  • domain assumption Lemma 3.5 [ADL+94]: degree and codegree regularity imply ε-regularity
    Basis of the unique-colorability certificate in Lemma 4.4; requires core size above a threshold.
  • domain assumption Björklund-Husfeldt-Koivisto eO(2^n) k-coloring algorithm [BHK09]
    Used as the exhaustive-search backstop for the exponentially rare non-okay graphs.
  • standard math McDiarmid, Chernoff, and hypergeometric tail concentration inequalities
    Used throughout Section 4 for the structural theorem (Theorem 8) and for the high-probability claims about good cores and linked graphs.
  • domain assumption Uniform distribution over labeled k-colorable graphs; conditioning on a proper coloring yields B_A with edge probability 1/2
    The model equivalence used in Section 4.4 to transfer from the planted model to the uniform distribution.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Graph k-Coloring in Average Sublinear Time." pith.science (2026). https://pith.science/paper/F46TKG3F

@misc{pith2026260726592,
  author       = {Pith},
  title        = {Pith review of: Graph k-Coloring in Average Sublinear Time},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/F46TKG3F}},
  note         = {Machine review of arXiv:2607.26592}
}
abstract

Graph $k$-coloring is one of the classic NP-complete problems. Previous work has studied its average time complexity, defined to be the average runtime of computing a $k$-coloring over the set of all $k$-colorable graphs on $n$ vertices. A highly influential result of Dyer-Frieze from 1989 gave an algorithm with $O(n^2)$ average runtime for constant $k$. This quadratic runtime appeared natural (and possibly even optimal) since almost all $k$-colorable graphs have $\Theta(n^2)$ edges, so one needs at least this time in order to read the (entire) input. However, this was later improved by Ku\v{c}era in 1995 to average runtime $O(n^2/k)$ for every $k \leq n^{c}$ where $c \in (0, 1)$. Nevertheless, in the most interesting case of $k = O(1)$, the best-known bound remained quadratic in $n$. The true average complexity of the $k$-coloring problem has remained elusive for the last three decades. We break the longstanding quadratic barrier. Our main result in this paper shows that the exact average-case complexity of this fundamental problem is $\Theta(nk)$ for every $k \leq n^{c'}$ and some $c' \in (0, 1)$. For $k = O(1)$, this reveals the average sublinear nature of $k$-colorability: the average-case complexity is linear in $n$, and thus sublinear in the size of the input. We further show that our $\Theta(nk)$ average runtime is optimal, since a simple bound proves that every algorithm that correctly $k$-colors all $k$-colorable graphs requires $\Omega(n k)$ average runtime. Our proofs draw on ideas from sublinear and local algorithms and also yield a local computation algorithm (LCA) for $k$-coloring with average-case probe complexity $\text{poly}(k)$. A key new ingredient in our algorithm is a method for certifying the unique colorability of random subgraphs, using tools from the theory of graph regularity.

Figures

Figures reproduced from arXiv: 2607.26592 by the authors.

Figure 1
Figure 1. Consider k-coloring for k = 3. Let the shaded circle be a uniquely colored good core. In Phase 2, for each vertex v not in the core, the algorithm samples vertices in the core to find adjacencies to vertices in all but one color class. If such adjacencies are found, v is then colored the remaining color. 3. (Phase 3) Finally, we enumerate over all remaining uncolored vertices. For each uncolored vertex v, we sample … view at source ↗
Figure 2
Figure 2. Consider k-coloring for k = 3. In Phase 3, for each vertex v not colored in an earlier phase, vertices in the good core and those colored in Phase 2 are sampled. If vertices of every color but one are found, v is colored with the remaining color. 2.1.2 Remaining Stages We handle the non-awesome graphs as follows. We keep the basic structure of Stage 1, but modify it in two main ways: 1. We now enumerate over all cor… view at source ↗
Figure 3
Figure 3. Consider k-coloring for k = 3. If B = Oe(k) extra vertices are not yet assigned a color, exhaustively search for the lexicographically first k-coloring of these vertices that is consistent with the partial coloring constructed so far. The formal algorithmic pseudocode for each of the phases is given in Section 5.1. The final k-coloring algorithm that combines these phases is given in Algorithm 11. 2.2 The Graph Stru… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Case 1: Towards contradiction, suppose there are two [PITH_FULL_IMAGE:figures/full_fig_p015_4.png]
Figure 5
Figure 5. Figure 5: Case 2: Towards contradiction, suppose there are two [PITH_FULL_IMAGE:figures/full_fig_p016_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

58 extracted references · 17 canonical work pages

  1. [1]

    Journal of Algorithms , volume=

    The solution of some random NP-hard problems in polynomial expected time , author=. Journal of Algorithms , volume=. 1989 , publisher=

    1989

  2. [2]

    Discrete Mathematics , volume =

    The tail of the hypergeometric distribution , author=. Discrete Mathematics , volume =. 1979 , issn =

    1979

  3. [3]

    Discrete Applied Mathematics , volume=

    Expected complexity of graph partitioning problems , author=. Discrete Applied Mathematics , volume=. 1995 , publisher=

    1995

  4. [4]

    Random Structures & Algorithms , volume=

    Exact and approximative algorithms for coloring G (n, p) , author=. Random Structures & Algorithms , volume=. 2004 , publisher=

    2004

  5. [5]

    Journal of Algorithms , volume=

    Coloring random and semi-random k-colorable graphs , author=. Journal of Algorithms , volume=. 1995 , publisher=

    1995

  6. [6]

    Discrete mathematics , volume=

    A note on coloring sparse random graphs , author=. Discrete mathematics , volume=. 2009 , publisher=

    2009

  7. [7]

    International Workshop on Graph-Theoretic Concepts in Computer Science , pages=

    Coloring k-colorable graphs in constant expected parallel time , author=. International Workshop on Graph-Theoretic Concepts in Computer Science , pages=. 1993 , organization=

    1993

  8. [8]

    Journal of algorithms , volume=

    Almost all k-colorable graphs are easy to color , author=. Journal of algorithms , volume=. 1988 , publisher=

    1988

Show all 58 references
  1. [9]

    Theory of Computing Systems , volume=

    Why almost all k-colorable graphs are easy to color , author=. Theory of Computing Systems , volume=. 2010 , publisher=

    2010

  2. [10]

    Journal of Algorithms , volume=

    Minimum coloring k-colorable graphs in polynomial average time , author=. Journal of Algorithms , volume=. 1999 , publisher=

    1999

  3. [11]

    50 Years of Integer Programming 1958-2008: from the Early Years to the State-of-the-Art , pages=

    Reducibility among combinatorial problems , author=. 50 Years of Integer Programming 1958-2008: from the Early Years to the State-of-the-Art , pages=. 2009 , publisher=

    1958

  4. [12]

    Information Processing Letters , volume=

    Deciding k-colorability in expected polynomial time , author=. Information Processing Letters , volume=. 2002 , publisher=

    2002

  5. [13]

    Uriel Feige and Joe Kilian , title =. J. Comput. Syst. Sci. , volume =

  6. [14]

    Karp , editor =

    Richard M. Karp , editor =. Reducibility Among Combinatorial Problems , booktitle =

  7. [15]

    A Fast Coloring Oracle for Average Case Hypergraphs , booktitle =

    Cassandra Marcussen and Edward Pyne and Ronitt Rubinfeld and Asaf Shapira and Shlomo Tauber , editor =. A Fast Coloring Oracle for Average Case Hypergraphs , booktitle =

  8. [16]

    Set Partitioning via Inclusion-Exclusion , journal =

    Andreas Bj. Set Partitioning via Inclusion-Exclusion , journal =. 2009 , url =. doi:10.1137/070683933 , timestamp =

    2009 doi

  9. [17]

    Fundamentals of Computation Theory: Proceedings of the 1977 International FCT-Conference, Pozna

    Expected behavior of graph coloring algorithms , author=. Fundamentals of Computation Theory: Proceedings of the 1977 International FCT-Conference, Pozna. 1977 , organization=

    1977

  10. [18]

    International Colloquium on Automata, Languages, and Programming , pages=

    Coloring semirandom graphs optimally , author=. International Colloquium on Automata, Languages, and Programming , pages=. 2004 , organization=

    2004

  11. [19]

    Proceedings of the twenty-sixth annual ACM symposium on Theory of Computing , pages=

    A spectral technique for coloring random 3-colorable graphs (preliminary version) , author=. Proceedings of the twenty-sixth annual ACM symposium on Theory of Computing , pages=

  12. [20]

    Journal of Computer and System Sciences , volume=

    Heuristics for semirandom graph problems , author=. Journal of Computer and System Sciences , volume=. 2001 , publisher=

    2001

  13. [21]

    arXiv preprint arXiv:2403.00129 , year=

    Beyond worst case local computation algorithms , author=. arXiv preprint arXiv:2403.00129 , year=

    arXiv

  14. [22]

    International Symposium on Mathematical Foundations of Computer Science , pages=

    Coloring sparse random k-colorable graphs in polynomial expected time , author=. International Symposium on Mathematical Foundations of Computer Science , pages=. 2005 , organization=

    2005

  15. [23]

    Random Structures & Algorithms , volume=

    Random I-colorable graphs , author=. Random Structures & Algorithms , volume=. 1995 , publisher=

    1995

  16. [24]

    Surveys in combinatorics , volume=

    On the method of bounded differences , author=. Surveys in combinatorics , volume=. 1989 , publisher=

    1989

  17. [25]

    Physical Review E—Statistical, Nonlinear, and Soft Matter Physics , volume=

    Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications , author=. Physical Review E—Statistical, Nonlinear, and Soft Matter Physics , volume=. 2011 , publisher=

    2011

  18. [26]

    Proceedings of the Seventeenth Annual

    Michael Krivelevich and Dan Vilenchik , title =. Proceedings of the Seventeenth Annual. 2006 , url =

    2006

  19. [27]

    Random Struct

    Yahav Alon and Michael Krivelevich , title =. Random Struct. Algorithms , volume =. 2020 , url =. doi:10.1002/RSA.20918 , timestamp =

    2020 doi

  20. [28]

    CoRR , volume =

    Michael Anastos , title =. CoRR , volume =. 2021 , url =. 2111.14771 , timestamp =

    2021 arXiv

  21. [29]

    Scott and Gregory B

    Alex D. Scott and Gregory B. Sorkin , editor =. Faster Algorithms for. APPROX/RANDOM 2003 , series =

    2003

  22. [30]

    Catellier and Tom Denat and Vangelis Th

    Nicolas Bourgeois and R. Catellier and Tom Denat and Vangelis Th. Paschos , title =. CoRR , volume =. 2015 , url =. 1505.04969 , timestamp =

    2015 arXiv

  23. [31]

    Duke and Hanno Lefmann and Vojtech R

    Noga Alon and Richard A. Duke and Hanno Lefmann and Vojtech R. The Algorithmic Aspects of the Regularity Lemma , journal =. 1994 , url =. doi:10.1006/JAGM.1994.1005 , timestamp =

    1994

  24. [32]

    Bandeira and Jess Banks and Dmitriy Kunisky and Cristopher Moore and Alexander S

    Afonso S. Bandeira and Jess Banks and Dmitriy Kunisky and Cristopher Moore and Alexander S. Wein , editor =. Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs , booktitle =. 2021 , url =

    2021

  25. [33]

    Semirandom Models as Benchmarks for Coloring Algorithms , booktitle =

    Michael Krivelevich and Dan Vilenchik , editor =. Semirandom Models as Benchmarks for Coloring Algorithms , booktitle =. 2006 , url =. doi:10.1137/1.9781611972962.4 , timestamp =

    2006 doi

  26. [34]

    Random Struct

    Dimitris Achlioptas and Ehud Friedgut , title =. Random Struct. Algorithms , volume =. 1999 , url =. doi:10.1002/(SICI)1098-2418(1999010)14:1\<63::AID-RSA3\>3.0.CO;2-7 , timestamp =

    1999 doi

  27. [35]

    Mathematics and Computer Science II: Algorithms, Trees, Combinatorics and Probabilities , pages=

    Coloring random graphs—an algorithmic perspective , author=. Mathematics and Computer Science II: Algorithms, Trees, Combinatorics and Probabilities , pages=. 2002 , publisher=

    2002

  28. [36]

    Solving NP-hard semirandom graph problems in polynomial expected time , journal =

    Amin Coja. Solving NP-hard semirandom graph problems in polynomial expected time , journal =. 2007 , url =. doi:10.1016/J.JALGOR.2004.07.003 , timestamp =

    2007 doi

  29. [37]

    On the tractability of coloring semirandom graphs , journal =

    Julia B. On the tractability of coloring semirandom graphs , journal =. 2008 , url =. doi:10.1016/J.IPL.2008.04.011 , timestamp =

    2008 doi

  30. [38]

    Algorithmic Barriers from Phase Transitions , booktitle =

    Dimitris Achlioptas and Amin Coja. Algorithmic Barriers from Phase Transitions , booktitle =. 2008 , url =. doi:10.1109/FOCS.2008.11 , timestamp =

    2008 doi

  31. [39]

    Upper-Bounding the k-Colorability Threshold by Counting Covers , journal =

    Amin Coja. Upper-Bounding the k-Colorability Threshold by Counting Covers , journal =. 2013 , url =. doi:10.37236/3337 , timestamp =

    2013 doi

  32. [40]

    Chasing the K-Colorability Threshold , booktitle =

    Amin Coja. Chasing the K-Colorability Threshold , booktitle =. 2013 , url =. doi:10.1109/FOCS.2013.48 , timestamp =

    2013 doi

  33. [41]

    The Condensation Phase Transition in Random Graph Coloring , booktitle =

    Victor Bapst and Amin Coja. The Condensation Phase Transition in Random Graph Coloring , booktitle =. 2014 , url =. doi:10.4230/LIPICS.APPROX-RANDOM.2014.449 , timestamp =

    2014 doi

  34. [42]

    Planting Colourings Silently , journal =

    Victor Bapst and Amin Coja. Planting Colourings Silently , journal =. 2017 , url =. doi:10.1017/S0963548316000390 , timestamp =

    2017 doi

  35. [43]

    CoRR , volume =

    Cassandra Marcussen and Ronitt Rubinfeld and Madhu Sudan , title =. CoRR , volume =. 2025 , url =. doi:10.48550/ARXIV.2508.16531 , eprinttype =. 2508.16531 , timestamp =

    2025 doi arXiv

  36. [44]

    Fast Local Computation Algorithms , booktitle =

    Ronitt Rubinfeld and Gil Tamir and Shai Vardi and Ning Xie , editor =. Fast Local Computation Algorithms , booktitle =. 2011 , url =

    2011

  37. [45]

    Space-efficient local computation algorithms , booktitle =

    Noga Alon and Ronitt Rubinfeld and Shai Vardi and Ning Xie , editor =. Space-efficient local computation algorithms , booktitle =. 2012 , url =. doi:10.1137/1.9781611973099.89 , timestamp =

    2012 doi

  38. [46]

    1992 , url =

    Nathan Linial , title =. 1992 , url =. doi:10.1137/0221015 , timestamp =

    1992 doi

  39. [47]

    Harris and Johannes Schneider and Hsin

    David G. Harris and Johannes Schneider and Hsin. Distributed (. J. 2018 , url =. doi:10.1145/3178120 , timestamp =

    2018 doi

  40. [48]

    2023 , url =

    Yannic Maus , title =. 2023 , url =. doi:10.1145/3605896 , timestamp =

    2023 doi

  41. [49]

    2019 , url =

    Distributed Coloring of Graphs with an Optimal Number of Colors , booktitle =. 2019 , url =. doi:10.4230/LIPICS.STACS.2019.10 , timestamp =

    2019 doi

  42. [50]

    A Distributed Palette Sparsification Theorem , booktitle =

    Maxime Flin and Mohsen Ghaffari and Magn. A Distributed Palette Sparsification Theorem , booktitle =. 2024 , url =. doi:10.1137/1.9781611977912.142 , timestamp =

    2024 doi

  43. [51]

    CoRR , volume =

    Andrzej Dorobisz and Jakub Kozik , title =. CoRR , volume =. 2021 , url =. 2103.10990 , timestamp =

    2021 arXiv

  44. [52]

    Local Computation Algorithms for Hypergraph Coloring - Following Beck's Approach , booktitle =

    Andrzej Dorobisz and Jakub Kozik , editor =. Local Computation Algorithms for Hypergraph Coloring - Following Beck's Approach , booktitle =. 2023 , url =. doi:10.4230/LIPICS.ICALP.2023.48 , timestamp =

    2023 doi

  45. [53]

    Sublinear Algorithms for (

    Sepehr Assadi and Yu Chen and Sanjeev Khanna , editor =. Sublinear Algorithms for (. Proceedings of the Thirtieth Annual. 2019 , url =. doi:10.1137/1.9781611975482.48 , timestamp =

    2019 doi

  46. [54]

    Palette Sparsification Beyond (

    Noga Alon and Sepehr Assadi , editor =. Palette Sparsification Beyond (. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques,. 2020 , url =. doi:10.4230/LIPICS.APPROX/RANDOM.2020.6 , timestamp =

    2020 doi

  47. [55]

    CoRR , volume =

    Asaf Ferber and Liam Hardiman and Xiaonan Chen , title =. CoRR , volume =. 2025 , url =. doi:10.48550/ARXIV.2502.06024 , eprinttype =. 2502.06024 , timestamp =

    2025 doi arXiv

  48. [56]

    TheoretiCS , volume =

    Sepehr Assadi and Helia Yazdanyar , title =. TheoretiCS , volume =. 2026 , url =. doi:10.46298/THEORETICS.26.3 , timestamp =

    2026 doi

  49. [57]

    Michal Parnas and Dana Ron , title =. Theor. Comput. Sci. , volume =. 2007 , url =. doi:10.1016/J.TCS.2007.04.040 , timestamp =

    2007 doi

  50. [58]

    The Complexity of (

    Yi. The Complexity of (. Proceedings of the 2019. 2019 , url =. doi:10.1145/3293611.3331607 , timestamp =

    2019

Pith tools

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