Browse › Theoretical computer science › 133 The computational complexity of Weisfeiler–Leman refinement
Unconditional time lower bounds for Weisfeiler–Leman equivalence
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
For every sufficiently large fixed k, deciding whether two n-vertex graphs are k-Weisfeiler–Leman equivalent requires $n^{\Omega(k)}$ deterministic sequential time in the worst case. The bound holds at every sufficiently large graph order, even for simple connected uncolored graphs of diameter at most two, without a complexity assumption. Inputs are explicit adjacency matrices; the models are multitape Turing machines and sequential logarithmic-word RAMs with fixed polynomial-bit-time instructions. Both joint and separate replacement conventions are covered.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Follow-up works
- Radu Curticapean, Mingjun Liu, Daniel Neuen, and Tim Seppelt, Lower Bounds for Weisfeiler–Leman (Zenodo:10.5281/zenodo.23213174, 2026-10-07). This concurrent AI-assisted manuscript cites the paper and states an unconditional exclusion of O(N^{k−1−δ}) deterministic multitape time for each fixed k ≥ 3 and δ > 0; its preface dates the AI-assisted results to September 19–29 and describes the manuscript as a hastily written public timestamp. [AI-generated per source] [family-level]
Formalization
- OpenAI, The computational complexity of Weisfeiler–Leman refinement: Lean scope notes (OpenAI Math Release, lean/docs/133.md, 2026-10-06). The release's Lean scope note says the unconditional $n^{ck}$ deterministic time lower bound is formalized at every sufficiently large order, for multitape Turing machines and log-word RAMs, both update conventions and connected diameter-two inputs, with comparator
WeisfeilerLeman.lean. [AI-generated per source] [family-level] - Radu Curticapean, Mingjun Liu, Daniel Neuen, and Tim Seppelt, Lean formalizations of Weisfeiler–Leman results (supplement to Zenodo:10.5281/zenodo.23213174, 2026-10-07). The archive documents WL/game/homomorphism correspondence, round bounds and a deterministic register compiler, with decision-complexity reductions outside its scope. [AI-generated per source] [family-level]
Related prior literature mentioned by others
- Martin Grohe, Moritz Lichter, Daniel Neuen, and Pascal Schweitzer, Compressing CFI Graphs and Lower Bounds for the Weisfeiler–Leman Refinements (arXiv:2308.11970v2, 2025-01-27; Journal of the ACM 72(3), 2025). Curticapean and coauthors cite its Ω(n^{k/2}) refinement-round bound as a predecessor to their concurrent work on this family. [family-level]
Possibly relevant literature (found by the agent, not checked)
- Christoph Berkholz, Paul Bonsma and Martin Grohe, Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement (arXiv:1509.08251, 2015; extended abstract ESA 2013). Proves an $O((m+n)\log n)$ lower bound for colour refinement within a broad class of refinement algorithms, a restricted-model counterpart to the paper's lower bound for every deterministic decider of $k$-WL equivalence.
News and blogs
- Tim Seppelt, News: Lower Bounds for Weisfeiler–Leman (author website, 2026-10-07). Seppelt announces the concurrent manuscript in response to OpenAI’s release and reports extensions involving classical complexity, parameterized complexity and iteration bounds. [family-level]
Elsewhere
- Emergent Mind: family 133
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Unconditional-time-lower-bounds-for-Weisfeiler-Leman-equivalence-September-25-2026,
author = {{OpenAI}},
title = {{Unconditional time lower bounds for Weisfeiler--Leman equivalence}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Unconditional-time-lower-bounds-for-Weisfeiler-Leman-equivalence-September-25-2026/paper.pdf}{OAI:Unconditional-time-lower-bounds-for-Weisfeiler-Leman-equivalence-September-25-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/133.md. The Lean statements have not been checked by people against the paper's claims.
Family 133: The computational complexity of Weisfeiler–Leman refinement
Proves unconditional $n^{\Omega(k)}$ deterministic time lower bounds for joint and separate k-dimensional Weisfeiler–Leman equivalence, for sufficiently large fixed k in the specified sequential adjacency-matrix models. With dimension as input, joint equivalence is EXPTIME-complete even on subcubic graphs; deciding whether refinement identifies a graph is also EXPTIME-complete.
Other papers in this family:
- Parity lifts and bounded-treewidth witnesses for Weisfeiler–Leman equivalence · September 25, 2026
- The complexity of identifying a graph by Weisfeiler–Leman refinement · September 25, 2026
- Variable-dimension Weisfeiler–Leman equivalence on general and subcubic graphs · September 25, 2026