Lower Bounds for the Weisfeiler–Leman Algorithm via Implicit Parity Systems
No public endorsements yet.
Loading review…
Sign in with ORCIDAbstract
The -dimensional Weisfeiler–Leman algorithm (-WL) is a simple combinatorial algorithm that was originally designed as a heuristic for the graph isomorphism problem, but which also has surprising connections to areas such as logic, homomorphism counts, linear programming, proof complexity, (symmetric) algebraic complexity, and machine learning. This submission formalizes the following lower bounds for WL:
- Time. For every fixed and , no deterministic multitape Turing machine decides whether -WL distinguishes two given colored graphs in time , where is the length of the binary encoding of the input pair. This almost matches the classical upper bound of . When is part of the input, the problem is -hard under polynomial-time many-one reductions, and -hard under fpt-reductions when parameterized by ; moreover, no deterministic multitape Turing machine decides it in time for some , where is the length of the encoded instance.
- Iteration number. On -vertex graphs, the iteration number of -WL is , matching the upper bound of Döring and Neuen.
- Witness size. There are pairs of -vertex graphs distinguished by -WL for which every graph of treewidth at most with has vertices. This is complemented by an upper bound of , also stated for uncolored graphs in the language of homomorphism indistinguishability.
All results are obtained via a unified framework. Implicit parity systems are succinctly represented systems of linear equations over . For each implicit parity system with coordinate blocks, the matrix compiler constructs a pair of graphs on which the bijective -pebble game, and hence -WL, exactly simulates unit propagation in the system. Deterministic computations are encoded into such systems by a recursive simulation due to Koucký, in which the calls of one recursion depth share their locations and the call paths are packed into the coordinate blocks; the reductions are carried out by explicit multitape Turing machines.
Everything is proved, including the pebble game and homomorphism characterizations of -WL, the stabilization bound of Döring and Neuen, the deterministic time hierarchy theorem (for polynomial bounds, and for the exponential bounds versus ), and the translations from the archive's single-tape and multi-stack machine models used for and many-one reductions. Membership of the problem in and is not formalized. The class and fpt-reductions are defined here with deterministic multitape Turing machines.
Concepts
- thm✓
ExponentialTimeHierarchy - thm✓
EXPTIMEHardness - thm✓
GameCharacterization - thm✓
HomomorphismCharacterization - thm✓
IterationNumber - thm✓
MachineTranslations - thm✓
MatrixCompiler - thm✓
PackedRepresentation - thm✓
RowSpaceCompiler - thm✓
RuntimeLowerBound - thm✓
Stabilization - thm✓
TimeHierarchy - thm✓
WitnessFromRounds - thm✓
WitnessLowerBound - thm✓
XPHardness - cor✓
ExponentialLowerBound - cor✓
UncoloredWitnessUpperBound - cor✓
WitnessUpperBound
- def
BinaryEncodings - def
ColoredGraphs - def
ColoredHomomorphisms - def
ContradictionTrees - def
DeterministicTime - def
ImplicitParitySystems - def
ImplicitSystemEncodings - def
ParameterizedComplexity - def
ParitySystems - def
PebbleGame - def
TreewidthClasses - def
WeisfeilerLeman - def
WLProblems
- def
Lax228581.Treewidth - def
Lax429075.Reductions - def
Lax434930.ExponentialTime - def
Lax434930.MachineModels - def
Lax434930.NondeterministicPolynomialTime - def
Lax434930.PolynomialTime - def
Lax489179.Algorithms - def
Lax489179.TuringMachine - def
Lax871432.GraphClasses - def
Lax871432.HomomorphismCounts - def
Lax871432.HomomorphismIndistinguishability - def
Lax871432.IsomorphismRelaxations
Concept map
Proofs
Proof networkview on GitHub
Proof list
-
⊢
Lax119563Proofs.Game.distinguishesAfter_of_spoilerWinsWithin -
⊢
Lax119563Proofs.Game.spoilerWinsWithin_of_distinguishesAfter
Lean sources for these proofs: proofs/ on GitHub
Proof code is not displayed; the archive records each proof's checked relationship between claims.
Related submissions
Submission map
Cite this
This is only the formalizers. The authors of the formalized results may be different (see References).
@misc{lax-119563,
author = {Radu Curticapean and Mingjun Liu and Daniel Neuen and Tim Seppelt},
title = {Lower Bounds for the Weisfeiler–Leman Algorithm via Implicit Parity Systems},
year = {2026},
howpublished = {Lax Archive, lax-119563},
url = {https://laxarchive.org/lax-119563/},
note = {draft},
}
References
- Yakov Shalunov. Improved Bounds on the Space Complexity of Circuit Evaluation. Electronic Colloquium on Computational Complexity TR25-078, 2025. eccc.weizmann.ac.il/report/2025/078/download
- Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Springer, 2006. doi:10.1007/3-540-29953-X
- Radu Curticapean, Mingjun Liu, Daniel Neuen and Tim Seppelt. Lower Bounds for Weisfeiler-Leman. Zenodo, 2026. doi:10.5281/zenodo.23213174 · doi.org/10.5281/zenodo.23213174
- Jin-Yi Cai, Martin Fürer and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica 12(4):389–410, 1992. doi:10.1007/BF01305232
- Neil Immerman and Eric Lander. Describing Graphs: A First-Order Approach to Graph Canonization. In Complexity Theory Retrospective 59–81, 1990. doi:10.1007/978-1-4612-4478-3_5
- Lauri Hella. Logical Hierarchies in PTIME. Information and Computation 129(1):1–19, 1996. doi:10.1006/inco.1996.0070
- Juris Hartmanis and Richard E. Stearns. On the Computational Complexity of Algorithms. Transactions of the American Mathematical Society 117:285–306, 1965. doi:10.1090/S0002-9947-1965-0170805-7
- F. C. Hennie and R. E. Stearns. Two-Tape Simulation of Multitape Turing Machines. Journal of the ACM 13(4):533–546, 1966.
- Zdeněk Dvořák. On recognizing graphs by numbers of homomorphisms. Journal of Graph Theory 64(4):330–342, 2010. doi:10.1002/jgt.20461
- Holger Dell, Martin Grohe and Gaurav Rattan. Lovász Meets Weisfeiler and Leman. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) 107:40:1–40:14, 2018. doi:10.4230/LIPIcs.ICALP.2018.40
- Simon Döring and Daniel Neuen. The Classical Weisfeiler-Leman Algorithm Stabilizes in Rounds. arXiv, 2026. arXiv:2609.17364 [cs.DS]. doi:10.48550/arXiv.2609.17364
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments