Browse › Theoretical computer science › 133 The computational complexity of Weisfeiler–Leman refinement
The complexity of identifying a graph by Weisfeiler–Leman refinement
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
We prove that deciding whether Weisfeiler–Leman refinement of an input dimension identifies a given graph is EXPTIME-complete. The input is a nonempty finite simple uncolored graph in adjacency-matrix form and a positive binary-encoded dimension. Identification quantifies over every comparison graph.
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.
Comments and discussion
- Radu Curticapean, Mingjun Liu, Daniel Neuen, and Tim Seppelt, Purpose and AI Statement (preface to Lower Bounds for Weisfeiler–Leman, 2026-10-07). The authors date their AI-assisted results to September 19–29 and describe the release-triggered 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 EXPTIME-completeness of deciding whether refinement of a positive binary-encoded dimension identifies a nonempty simple uncolored adjacency-matrix graph is formalized, covering both the upper bound and many-one hardness, with comparator
WLIdentification.lean. [AI-generated per source] [family-level]
Possibly relevant literature (found by the agent, not checked)
- Phokion G. Kolaitis and Jonathan Panttaja, On the Complexity of Existential Pebble Games (CSL 2003, LNCS, pp. 314–329, doi:10.1007/978-3-540-45220-1_26). According to later citations, this work shows that deciding the existential $k$-pebble game is EXPTIME-complete when $k$ is part of the input, an analogue for a different game of the paper's EXPTIME-hardness with the dimension as input.
- Thomas Schneider and Pascal Schweitzer, An Upper Bound on the Weisfeiler-Leman Dimension (ICALP 2025, 2025-06-30). Its universal identification-dimension bound of 0.15n + o(n) may contextualize the manuscript’s dimension-capping argument for the EXPTIME upper bound.
Elsewhere
- Emergent Mind: family 133
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:The-complexity-of-identifying-a-graph-by-Weisfeiler-Leman-refinement-September-25-2026,
author = {{OpenAI}},
title = {{The complexity of identifying a graph by Weisfeiler--Leman refinement}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/The-complexity-of-identifying-a-graph-by-Weisfeiler-Leman-refinement-September-25-2026/paper.pdf}{OAI:The-complexity-of-identifying-a-graph-by-Weisfeiler-Leman-refinement-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
- Unconditional time lower bounds for Weisfeiler–Leman equivalence · September 25, 2026
- Variable-dimension Weisfeiler–Leman equivalence on general and subcubic graphs · September 25, 2026