Pith. sign in

REVIEW 2 major objections 3 minor 1 cited by

k-Coloring is Faster than Computing the Chromatic Number

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

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

Pith's one-line read For every fixed number of colors k, the paper proves that k-coloring an n-vertex graph admits a randomized algorithm running in (2−ε_k)^n time for some positive ε_k, strictly faster than the general 2^n bound for computing the chromatic num

desk verdict The main theorem is genuine and the proof is far more than a sketch, but the general bootstrap leans on the un-reproduced two-block theorem from Zamir's STOC 2023 paper, and that is exactly where a referee should push hard. read the letter →

arxiv 2607.25973 v1 pith:7KOS2YO2 submitted 2026-07-28 cs.DS

Or Zamir This is my paper · ORCID
classification cs.DS MSC 05C1568Q2568W20
keywords graphcoloringlistexponential-timealgorithmsfixedpalettebootstrapreductionrandomizedsubsetconvolutiontwo-blockrestrictions
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 tries to prove that for every fixed number of colors k, deciding whether an n-vertex graph is k-colorable can be done in $(2 - \varepsilon_k)^n$ randomized time for some positive $\varepsilon_k$ — strictly faster than the $2^n$ time needed to compute the chromatic number in general. It achieves this by turning list-coloring itself into a bootstrapping device: from any sub-$2^n$ algorithm for $(k-1)$-list-coloring over a fixed palette, it builds a sub-$2^n$ algorithm for k-list-coloring over the same palette. The significance is that this removes a long-standing gap: previously only $k \le 6$ had such improvements, while general chromatic-number computation remained the best known for all larger k. If correct, every fixed-size coloring and list-coloring problem over a fixed palette has a strictly better-than-$2^n$ worst-case algorithm, matching the qualitative situation for $k$-SAT.

What carries the argument

The central mechanisms are (1) a seed-shortening lemma that, via randomized sampling and enumeration, either finds a coloring or reduces all remaining lists by one color; (2) a pigeonhole argument on the constant-sized complement sets $Q_v = P \setminus L(v)$, producing two linear-size 'supported' vertex sets $A_Q$ (lists $\subseteq Q$) and $B_R$ (lists $\subseteq R$); (3) a two-block restricted-coloring black box (based on the Extensions-Sum machinery) that decides colorability with allowed color domains in $O^*(2^{|D_Q|}+2^{|D_R|})$ time; and (4) a binary-list interpolation algorithm that solves instances with many size-two lists in $O^*(2^{n-b/M})$ time. The bootstrap stitches these together so each step preserves a linear prog

What would settle it

A counterexample to the two-block restricted-coloring claim, or a concrete list-coloring instance where a completed bootstrap step violates the invariant that $|A_Q|$ grows by $r$ and $|B_R|$ never drops below $\gamma n$, would settle the matter. On the lower-bound side, an unconditional proof that some fixed $k$-coloring requires $2^{\Omega(n)}$ time would refute the theorem.

Watch

Extended reading notes

Core claim

The central claim is that k-coloring on n-vertex graphs admits a randomized algorithm running in time $(2 - \varepsilon_k)^n$ for every fixed k, equivalently for list-coloring over a fixed palette of size K. The proof constructs an iterable reduction: assuming a sub-$2^n$ algorithm for $(k-1)$-list-coloring over a fixed palette P, one obtains a sub-$2^n$ algorithm for k-list-coloring over P. The reduction samples small random vertex sets to shorten color lists, pigeonholes the finitely many list-complements to find a linear-size set of vertices sharing the same two-block partition $Q \cup R$ of the palette, and then uses a two-block restricted-coloring black box to combine colorings on the two supported sets in sub-2^

Load-bearing premise

The load-bearing premise is the correctness of the two-block restricted-coloring black box (Theorem 3.7), which states that colorability with allowed color domains can be decided in $O^*(2^{|D_Q|}+2^{|D_R|})$ time for any partition of the palette; if this theorem has a hidden condition or fails for the supported sets produced by the bootstrap, the whole iterated reduction collapses.

Editorial extensions

If this is right

  • Every fixed k now has a randomized sub-2^n k-coloring algorithm, answering a question open for all k>6.
  • List-coloring over a fixed palette of size K is solvable in (2−ε_K)^n time, which also covers k-coloring with K=k.
  • As a corollary of the warm-up, 7-coloring gets the first (2−ε)^n algorithm, via the new interpolation theorem for instances with many size-two lists.
  • The new binary-list interpolation algorithm is a standalone tool: instances with b vertices on lists of size at most two over a fixed palette run in O*(2^{n-b/M}) time.
  • If the bootstrap is iterated from the polynomial-time 2-list-coloring algorithm, it yields the claimed algorithms for all K; no base-saving assumption beyond the two stated black boxes is needed.

Reading between the lines

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

  • If the open question of a palette-independent q<2 for binary-list interpolation is resolved positively, the fixed-palette restriction could likely be lifted to give sub-2^n algorithms for k-list-coloring with unbounded palettes.
  • The paper's quantitative estimate that 1/ε_K grows like a tower of height Θ(K) suggests the actual savings are tiny for large K; future work may focus on improving this tower dependence, paralleling the history of k-SAT constants.
  • The ETH-based lower bound ruling out q=1 for interpolation hints that a fundamental trade-off between list length and palette size may be intrinsic, not an artifact of the proof.
  • A derandomization of the main randomized algorithm, or a polynomial-space version, would be natural next steps; the current method relies on exponentially small failure probability and exponential space via the two-block black box.
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

2 major / 3 minor

Summary. The paper proves that for every fixed k, k-coloring on n-vertex graphs admits a randomized algorithm with running time (2−ε_k)^n, and more generally that list-coloring over a fixed palette of size K admits such an algorithm. The proof establishes a bootstrap: from a sub-2^n algorithm for (k−1)-list-coloring over a fixed palette P, it constructs one for k-list-coloring over P. A warm-up handles one new gap by producing many vertices with lists of size two and applying a new deterministic interpolation algorithm (Theorem 4.4); the general bootstrap (Theorem 5.1) produces two large sets of vertices whose lists are supported on complementary subpalettes and combines them using a two-block restricted-coloring black box (Corollary 3.8). Iterating from polynomial-time 2-list-coloring yields Theorem 5.2. Section 4.4 gives an ETH-based lower bound showing that the interpolation parameter cannot be improved to q=1 with a palette-independent constant. Section 6 provides an informal quantitative estimate of the saving.

Significance. Should the result be correct, it resolves a long-standing gap: for every fixed k, k-coloring is strictly easier than the O*(2^n) algorithm for chromatic number, matching the qualitative situation for k-SAT. The paper is largely self-contained beyond two cited black boxes; it includes pseudocode for the reductions, explicit constants, a deterministic interpolation algorithm, and a conditional lower bound. The main theorem has a clear falsifiable consequence—an algorithm for every fixed k with an improved base—and the paper identifies concrete open problems, including palette-independent list coloring and quantitative improvements to ε_k. The proof's new machinery (seed shortening, pair-complement bootstrap, two supported sets) is substantial. The main risk is the reliance on the imported two-block theorem.

major comments (2)
  1. [§3.6, Theorem 3.7/Corollary 3.8; used in §5.1] The entire general bootstrap depends on the two-block restricted-coloring black box. The manuscript gives a one-paragraph indication that Theorem 3.7 follows from Lemmas 3.11, 3.14, 3.16 and Observation 3.23 of [Zam23], but does not reproduce the argument or state the exact theorem in [Zam23] with its hypotheses. Corollary 3.8 then plugs arbitrary list domains into this theorem. Since the terminal call of Theorem 5.1 is the only place where the two linear supported sets A_Q and B_R are combined, and no alternative combination argument is provided, the main theorem is exactly as secure as this imported theorem. Please include a complete proof of Theorem 3.7, or a precise statement of the corresponding theorem/lemmas in [Zam23] with a step-by-step derivation of the O*(2^{|D_Q|}+2^{|D_R|}) bound, and confirm that no hidden conditions on the domains V_c or the partition Q∪R are needed. This
  2. [§5.1, Theorem 5.1] The proof of Theorem 5.1 introduces the constant Ntr = ceil(2n/p0^m) for the number of independent trials. It is correct that p0^{-m} ≤ 2^{λdn} and that the total running-time exponents are κ+λd, 1−d+λd, and 1−γ+λd. However, the argument is compressed and the reader must reconstruct how the failure probability e^{-n} follows from a success probability of at least (1/2)p0^m per trial while only the favorable Q is guaranteed to have this property. I verified the calculation, but I recommend making the role of the favorable Q and the union over Q explicit in the text, since this is load-bearing for the claimed sub-2^n time bound.
minor comments (3)
  1. [Appendix A] The appendix states that an AI model 'reproduced (or copied)' the proof of [BHKK07] and displayed 'severe lack of attribution.' The final manuscript does cite [BHKK07] in Lemma 3.3, so I do not treat this as a technical defect. However, the wording should be reconciled with the paper's attribution practices and with the journal's AI-use policy.
  2. [Section 6] Section 6 is explicitly informal and not needed for the main theorems. If Proposition 6.1 is meant to be a formal statement, it should be labeled as such and proved with the constants tracked; if it is only a heuristic estimate, the informal status should be stated at the start of the section, not only in the surrounding prose.
  3. [Algorithms 1 and 3] The pseudocode uses the phrase 'if EasySolver-E(I) finds a coloring then return YES.' The easy solver is sometimes described as a decision algorithm; the decision-to-search conversion of Lemma 3.1 is invoked in the main text but not explicitly in the pseudocode. Aligning the pseudocode with Lemma 3.1 would avoid ambiguity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the sub-2^n k-coloring result is derived from polynomial 2-list-coloring by iterated reductions; self-citations are to independent prior theorems.

full rationale

The derivation chain is self-contained from the stated base case. Theorem 5.2 is obtained by applying Theorem 5.1 successively for k = 3,...,K, starting from polynomial-time 2-list-coloring (2-SAT). The bootstrap step reduces k-list-coloring to (k-1)-list-coloring using only (i) the seed-shortening lemma proved in this paper, (ii) the bounded-degree list-coloring theorem of [Zam21] (Theorem 3.5), and (iii) the two-block restricted-coloring theorem of [Zam23] (Theorem 3.7, via Corollary 3.8). These are parameter-free theorems whose stated assumptions do not include the target result (sub-2^n k-coloring for all k); they are external computational results with proofs in prior works, not re-statements of the conclusion. The paper does not fit any parameter to data and then relabel it a prediction; the only constants are existential choices in the proof. The warm-up interpolation (Theorem 4.4) is proved directly via all-induced-subinstance coloring and 2-SAT, and the ETH lower bound (Proposition 4.5) gives independent evidence that the interpolation constant cannot be 1, showing the savings are not vacuous. The main possible weakness — that Theorem 3.7 is imported from [Zam23] without reproducing its proof — is a correctness/verification risk, not a circularity: the present derivation does not assume k-coloring has a sub-2^n algorithm. No circular step was found.

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

The central claim rests on external theorems from the same author's earlier papers and standard results; these are used as black boxes. The proof itself introduces no empirical free parameters or new postulated entities.

assumptions (5)
  • domain assumption Theorem 3.5 (bounded-degree list coloring): For every fixed k, α, Δ>0, k-list-coloring on an (α,Δ)-bounded graph, with any palette, runs in O*(C^n) for some C<2.
    Used as the easy solver when a constant fraction of vertices have low degree; imported from [Zam21, Theorem 1.3].
  • domain assumption Theorem 3.7 (two-block restricted coloring): For palette P=Q∪R and allowed domains V_c, colorability with each c used only on V_c is decidable in O*(2^{|D_Q|}+2^{|D_R|}) time and exponential space.
    Terminal solver in the bootstrap via Corollary 3.8; imported from [Zam23] (Lemmas 3.11, 3.14, 3.16, Obs 3.23).
  • domain assumption Lemma 3.3 (all induced list subinstances): for fixed palette P, the colorability of every induced subgraph can be determined in O*(2^{|V|}) time.
    Used in the binary-list interpolation algorithm; extension of [BHKK07]/[BHK09].
  • domain assumption Traxler's ETH lower bound: there is a constant c>0 such that (d,2)-CSP with bounded frequency requires d^{c n} time for every fixed d under ETH.
    Used in Proposition 4.5 to rule out q=1 in binary-list interpolation.
  • standard math 2-SAT solvability in polynomial time.
    Used in the interpolation algorithm and as the base case for the bootstrap (2-list-coloring is 2-SAT).

how reviews work

0 comments
Cite this review

Pith. "Pith review of k-Coloring is Faster than Computing the Chromatic Number." pith.science (2026). https://pith.science/paper/7KOS2YO2

@misc{pith2026260725973,
  author       = {Pith},
  title        = {Pith review of: k-Coloring is Faster than Computing the Chromatic Number},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7KOS2YO2}},
  note         = {Machine review of arXiv:2607.25973}
}
abstract

We prove that $k$-coloring on $n$-vertex graphs has a randomized algorithm running in time $(2-\varepsilon_k)^n$, where $\varepsilon_k>0$ for every fixed $k$. Previously, only the cases $k\leq 6$ were known to have faster solutions than the general $O^\star\bigl(2^n\bigr)$ time algorithm of [Bj\"{o}rklund, Husfeldt, Koivisto, SICOMP 2009] that computes the chromatic number. We resolve this long-standing open problem by generalizing and combining tools from the $(k+2)$-coloring to $k$-list-coloring reduction of [Zamir, ICALP 2021] and the hypergraph-containers based approach in [Zamir, STOC 2023]. Together with new algorithms for list-coloring instances mixing long and short color lists, this yields an iterable reduction from $(k+1)$-list-coloring to $k$-list-coloring over fixed palettes.

Figures

Figures reproduced from arXiv: 2607.25973 by the authors.

Figure 1
Figure 1. An eligible vertex v under the witness c. In the following Section 4.3, we show that I can be solved deterministically in O∗ (2w(I) ) time. We next describe a lucky move that decreases w. Let I be a fully normalized current instance. Choose a uniformly random vertex v, and abort the move unless v is active and deg(v) > ∆. For such a vertex, let Qv = P \ L(v); because |L(v)| = K − 2, the set Qv has size two. Choose a… view at source ↗
Figure 2
Figure 2. The decomposition used by the binary-list interpolation algorithm. [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗
Figure 3
Figure 3. Encoding one forbidden assignment of a binary CSP constraint. Each CSP variable [PITH_FULL_IMAGE:figures/full_fig_p022_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The same two boundaries in two views. The supported sets [PITH_FULL_IMAGE:figures/full_fig_p024_4.png]

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

  1. Breaking the $2^n$ barrier for graph $k$-coloring

    cs.DS 2026-07 accept novelty 7.0 of 10

    Graph k-coloring admits a randomized one-sided-error algorithm in O((2−ε_k)^n) time for every fixed k, breaking the classical 2^n barrier.

Reference graph

Works this paper leans on

60 extracted references · 4 canonical work pages · cited by 1 Pith paper

  1. [1]

    and Tarjan, Robert Endre , title =

    Aspvall, Bengt and Plass, Michael F. and Tarjan, Robert Endre , title =. Information Processing Letters , volume =. 1979 , doi =

    1979

  2. [2]

    Journal of Algorithms , volume =

    Beigel, Richard and Eppstein, David , title =. Journal of Algorithms , volume =. 2005 , doi =

    2005

  3. [3]

    Fourier Meets

    Bj. Fourier Meets. Proceedings of the 39th Annual. 2007 , isbn =. doi:10.1145/1250790.1250801 , url =

    arXiv 2007

  4. [4]

    Set Partitioning via Inclusion--Exclusion , journal =

    Bj. Set Partitioning via Inclusion--Exclusion , journal =. 2009 , doi =

    2009

  5. [5]

    Parameterized and Exact Computation: Third International Workshop,

    Traxler, Patrick , title =. Parameterized and Exact Computation: Third International Workshop,. 2008 , doi =

    2008

  6. [6]

    30th Annual European Symposium on Algorithms (

    Zamir, Or , title =. 30th Annual European Symposium on Algorithms (. 2022 , doi =

    2022

  7. [7]

    48th International Colloquium on Automata, Languages, and Programming (

    Zamir, Or , title =. 48th International Colloquium on Automata, Languages, and Programming (. 2021 , doi =

    2021

  8. [8]

    Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages =

    Zamir, Or , title =. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages =. 2023 , doi =

    2023

Show all 60 references
  1. [9]

    AI magazine , volume=

    Algorithms for constraint-satisfaction problems: A survey , author=. AI magazine , volume=

  2. [10]

    A probabilistic algorithm for

    Schoning, T , booktitle=. A probabilistic algorithm for. 1999 , organization=

    1999

  3. [11]

    Proc.\ of 41st ICALP

    Timon Hertli , title =. Proc.\ of 41st ICALP. 2014 , url =. doi:10.1007/978-3-662-43948-7\_50 , timestamp =

    2014 doi

  4. [12]

    Timon Hertli , title =

  5. [13]

    Russell Impagliazzo and Ramamohan Paturi , title =. J. Comput. Syst. Sci. , volume =. 2001 , url =. doi:10.1006/jcss.2000.1727 , timestamp =

    2001

  6. [14]

    Discrete Applied Mathematics , volume =

    Burkhard Monien and Ewald Speckenmeyer , title =. Discrete Applied Mathematics , volume =. 1985 , url =. doi:10.1016/0166-218X(85)90050-2 , timestamp =

    1985 doi

  7. [15]

    Satisfiability Coding Lemma , journal =

    Ramamohan Paturi and Pavel Pudl. Satisfiability Coding Lemma , journal =. 1999 , url =

    1999

  8. [16]

    An Improved Exponential-Time Algorithm for k -

    Ramamohan Paturi and Pavel Pudl. An Improved Exponential-Time Algorithm for k -. 39th Annual Symposium on Foundations of Computer Science,. 1998 , url =. doi:10.1109/SFCS.1998.743513 , timestamp =

    1998

  9. [17]

    An improved exponential-time algorithm for k -

    Ramamohan Paturi and Pavel Pudl. An improved exponential-time algorithm for k -. J. 2005 , Note =. doi:10.1145/1066100.1066101 , timestamp =

    2005

  10. [18]

    Proc.\ of 44th ICALP , pages =

    Pavel Pudl. Proc.\ of 44th ICALP , pages =. 2017 , volume =. doi:10.4230/LIPIcs.ICALP.2017.85 , annote =

    2017 doi

  11. [19]

    An Improvement of the Algorithm of

    Qin, Tong and Watanabe, Osamu , booktitle=. An Improvement of the Algorithm of. 2018 , organization=

    2018

  12. [20]

    A New Approach on Solving 3-Satisfiability , booktitle =

    Robert. A New Approach on Solving 3-Satisfiability , booktitle =. 1996 , url =. doi:10.1007/3-540-61732-9\_59 , timestamp =

    1996 doi

  13. [21]

    Steinberger , title =

    Dominik Scheder and John P. Steinberger , title =. 32nd Computational Complexity Conference,. 2017 , url =. doi:10.4230/LIPIcs.CCC.2017.9 , timestamp =

    2017 doi

  14. [22]

    Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Faster k-sat algorithms using biased-ppsz , author=. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages=

  15. [23]

    3-coloring in time

    Beigel, Richard and Eppstein, David , journal=. 3-coloring in time. 2005 , publisher=

    2005

  16. [24]

    ACM Transactions on Algorithms (TALG) , volume=

    Families with infants: speeding up algorithms for NP-hard problems using FFT , author=. ACM Transactions on Algorithms (TALG) , volume=. 2016 , publisher=

    2016

  17. [25]

    International Computing and Combinatorics Conference , pages=

    Improved exact algorithms for counting 3-and 4-colorings , author=. International Computing and Combinatorics Conference , pages=. 2007 , organization=

    2007

  18. [26]

    Information and Computation , volume=

    Faster exponential-time algorithms in graphs of bounded average degree , author=. Information and Computation , volume=. 2015 , publisher=

    2015

  19. [27]

    Graph colouring algorithms , DOI=

    Husfeldt, Thore , editor=. Graph colouring algorithms , DOI=. Topics in Chromatic Graph Theory , publisher=. 2015 , pages=

    2015

  20. [28]

    On the foundations of combinatorial theory I

    Rota, Gian-Carlo , journal=. On the foundations of combinatorial theory I. Theory of M. 1964 , publisher=

    1964

  21. [29]

    1937 , publisher=

    The design and analysis of factorial experiments , author=. 1937 , publisher=

    1937

  22. [30]

    The art of computer programming , volume=

    Seminumerical algorithms , author=. The art of computer programming , volume=. 1997 , publisher=

    1997

  23. [31]

    IEEE Transactions on Systems, Man, and Cybernetics , volume=

    Computational aspects of the Mobius transformation of graphs , author=. IEEE Transactions on Systems, Man, and Cybernetics , volume=. 1992 , publisher=

    1992

  24. [32]

    , author=

    A Note on the Complexity of the Chromatic Number Problem. , author=

  25. [33]

    Complexity of computer computations , pages=

    Reducibility among combinatorial problems , author=. Complexity of computer computations , pages=. 1972 , publisher=

    1972

  26. [34]

    Coverings and colorings of hypergraphs , author=. Proc. 4th Southeastern Conference of Combinatorics, Graph Theory, and Computing , pages=. 1973 , organization=

    1973

  27. [35]

    ACM Sigact News , volume=

    Planar 3-colorability is polynomial complete , author=. ACM Sigact News , volume=. 1973 , publisher=

    1973

  28. [36]

    On the complexity of

    Impagliazzo, Russell and Paturi, Ramamohan , journal=. On the complexity of. 2001 , publisher=

    2001

  29. [37]

    Exact algorithms for

    Woeginger, Gerhard J , booktitle=. Exact algorithms for. 2003 , publisher=

    2003

  30. [38]

    Operations Research Letters , volume=

    Enumerating maximal independent sets with applications to graph colouring , author=. Operations Research Letters , volume=. 2004 , publisher=

    2004

  31. [39]

    Israel journal of Mathematics , volume=

    On cliques in graphs , author=. Israel journal of Mathematics , volume=. 1965 , publisher=

    1965

  32. [40]

    IRE Transactions on Electronic Computers , number=

    Minimizing the number of states in incompletely specified sequential switching functions , author=. IRE Transactions on Electronic Computers , number=. 1959 , publisher=

    1959

  33. [41]

    Workshop on Algorithms and Data Structures , pages=

    Small maximal independent sets and faster exact graph coloring , author=. Workshop on Algorithms and Data Structures , pages=. 2001 , organization=

    2001

  34. [42]

    Deciding 3-colourability in less than

    Schiermeyer, Ingo , booktitle=. Deciding 3-colourability in less than. 1993 , organization=

    1993

  35. [43]

    Communications of the ACM , volume=

    Exact exponential algorithms , author=. Communications of the ACM , volume=. 2013 , publisher=

    2013

  36. [44]

    2010 , publisher=

    Exact Exponential Algorithms , author=. 2010 , publisher=

    2010

  37. [45]

    Journal of Computer and System Sciences , volume =

    Russell Impagliazzo and Ramamohan Paturi and Francis Zane , title =. Journal of Computer and System Sciences , volume =. 2001 , doi =

    2001

  38. [46]

    On Problems as Hard as

    Marek Cygan and Holger Dell and Daniel Lokshtanov and D. On Problems as Hard as. ACM Transactions on Algorithms , volume =. 2016 , doi =

    2016

  39. [47]

    Ryan Williams , title =

    Virginia Vassilevska Williams and R. Ryan Williams , title =. Journal of the ACM , volume =. 2018 , doi =

    2018

  40. [48]

    Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science , pages =

    Amir Abboud and Virginia Vassilevska Williams , title =. Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science , pages =. 2014 , doi =

    2014

  41. [49]

    Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing , pages =

    Arturs Backurs and Piotr Indyk , title =. Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing , pages =. 2015 , doi =

    2015

  42. [50]

    Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science , pages =

    Karl Bringmann , title =. Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science , pages =. 2014 , doi =

    2014

  43. [51]

    Proceedings of the International Congress of Mathematicians 2018 , pages =

    Virginia Vassilevska Williams , title =. Proceedings of the International Congress of Mathematicians 2018 , pages =. 2018 , doi =

    2018

  44. [52]

    Ryan Williams , title =

    Nikhil Vyas and R. Ryan Williams , title =. Journal of Artificial Intelligence Research , volume =. 2021 , doi =

    2021

  45. [53]

    Theory of Computing Systems , volume=

    Trimmed Moebius inversion and graphs of bounded degree , author=. Theory of Computing Systems , volume=. 2010 , publisher=

    2010

  46. [54]

    Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture , booktitle =

    Andreas Bj. Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture , booktitle =. 2025 , doi =

    2025

  47. [55]

    The Asymptotic Rank Conjecture and the Set Cover Conjecture Are Not Both True , booktitle =

    Andreas Bj. The Asymptotic Rank Conjecture and the Set Cover Conjecture Are Not Both True , booktitle =. 2024 , doi =

    2024

  48. [56]

    Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC) , pages =

    Kevin Pratt , title =. Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC) , pages =. 2024 , doi =

    2024

  49. [57]

    32nd Annual European Symposium on Algorithms (ESA 2024) , pages=

    A faster algorithm for the 4-coloring problem , author=. 32nd Annual European Symposium on Algorithms (ESA 2024) , pages=. 2024 , organization=

    2024

  50. [58]

    3-Coloring in Time O (1.3217\^

    Meijer, Lucas , journal=. 3-Coloring in Time O (1.3217\^

  51. [59]

    Lee , title =

    Serge Gaspers and Edward J. Lee , title =. Algorithmica , volume =. 2023 , doi =

    2023

  52. [60]

    Theoretical Computer Science , volume =

    Pu Wu and Huanyu Gu and Huiqin Jiang and Zehui Shao and Jin Xu , title =. Theoretical Computer Science , volume =. 2026 , doi =

    2026

Pith tools

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