While this submission is a draft, it cannot be used by other submissions.

Lower Bounds for the Weisfeiler–Leman Algorithm via Implicit Parity Systems

lax-119563·formalized by Radu Curticapean @radomite · Mingjun Liu @hld67890 · Daniel Neuen @DanielN64 · Tim Seppelt @tseppelt·created ·GitHub @c666309·Lean v4.33.0 epoch · mathlib db584cd6d46c

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    The kk-dimensional Weisfeiler–Leman algorithm (kk-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 k≥3k \geq 3 and ε>0\varepsilon > 0, no deterministic multitape Turing machine decides whether kk-WL distinguishes two given colored graphs in time O(nk−1−ε)O(n^{k-1-\varepsilon}), where nn is the length of the binary encoding of the input pair. This almost matches the classical upper bound of O(nk+1log⁡n)O(n^{k+1} \log n). When kk is part of the input, the problem is EXPTIME\mathsf{EXPTIME}-hard under polynomial-time many-one reductions, and XP\mathsf{XP}-hard under fpt-reductions when parameterized by kk; moreover, no deterministic multitape Turing machine decides it in time O(2εN1/5)O(2^{\varepsilon N^{1/5}}) for some ε>0\varepsilon > 0, where NN is the length of the encoded instance.
    • Iteration number. On nn-vertex graphs, the iteration number of kk-WL is Ωk(nk−1)\Omega_k(n^{k-1}), matching the upper bound of Döring and Neuen.
    • Witness size. There are pairs of nn-vertex graphs distinguished by kk-WL for which every graph FF of treewidth at most kk with hom⁡(F,G0)≠hom⁡(F,G1)\hom(F, G_0) \neq \hom(F, G_1) has 2Ωk(nk−1)2^{\Omega_k(n^{k-1})} vertices. This is complemented by an upper bound of 2Ok(nk−1log⁡n)2^{O_k(n^{k-1} \log n)}, 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 F2\mathbb F_2. For each implicit parity system with kk coordinate blocks, the matrix compiler constructs a pair of graphs on which the bijective (k+1)(k+1)-pebble game, and hence kk-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 kk-WL, the stabilization bound of Döring and Neuen, the deterministic time hierarchy theorem (for polynomial bounds, and for the exponential bounds 2n2^n versus 2n/42^{n/4}), and the translations from the archive's single-tape and multi-stack machine models used for EXPTIME\mathsf{EXPTIME} and many-one reductions. Membership of the problem in EXPTIME\mathsf{EXPTIME} and XP\mathsf{XP} is not formalized. The class XP\mathsf{XP} and fpt-reductions are defined here with deterministic multitape Turing machines.

    Concepts

    Concept map
    44 concepts
    100%
    Binary encodings of numbers and graph pairsColored graphsHomomorphism counts and treewidth ofcolored graphsDerivation and contradiction treesDeterministic multitape Turing machines andrunning timeWL Distinguishing is EXPTIME-hardAn exponential time lower bound for WLDistinguishingThe deterministic time hierarchy theorem forexponential timeThe pebble game characterization ofWeisfeiler–LemanThe homomorphism characterization ofWeisfeiler–LemanImplicit parity systemsBinary encodings of implicit parity systemsA lower bound on the iteration number ofk-WLTranslations between machine modelsThe matrix compilerPacked implicit parity systems fordeterministic computationsParameterized problems, XP andfpt-reductionsParity systems and unit propagationThe bijective pebble gameThe row-space compilerAn unconditional time lower bound for k-WLDistinguishingStabilization of k-WLThe deterministic time hierarchy theoremGraphs of bounded treewidthAn upper bound on the size ofhomomorphism witnesses for uncoloredgraphsWL Distinguishing as a language and as aparameterized problemThe Weisfeiler–Leman algorithmHomomorphism witnesses from roundsA lower bound on the size of homomorphismwitnessesAn upper bound on the size ofhomomorphism witnessesWL Distinguishing is XP-hardTreewidthPolynomial many-one reductions andNP-completenessBinary encoding of an input and a certificateThe complexity class EXPTIMEFinite-stack and elementary single-tapedefinitions of PThe complexity class NPThe complexity class PDeterministic and bounded-error algorithmsFinite multitape Turing machinesGraph classesHomomorphism countsHomomorphism indistinguishabilityGraph isomorphism relaxations
    Proven claimDefinitionThis submissionOther submissionA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.

    Proofs

    Proof networkview on GitHub

    100%
    premise files concept fileProven claimClaim from this submissionAll proofs of one concept — hover for individual statements and proofs
    Proof list

    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

    100%
    This submissionOther submissionA → B: B's concepts build on A

    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

    1. 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
    2. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Springer, 2006. doi:10.1007/3-540-29953-X
    3. 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
    4. 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
    5. 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
    6. Lauri Hella. Logical Hierarchies in PTIME. Information and Computation 129(1):1–19, 1996. doi:10.1006/inco.1996.0070
    7. 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
    8. F. C. Hennie and R. E. Stearns. Two-Tape Simulation of Multitape Turing Machines. Journal of the ACM 13(4):533–546, 1966.
    9. 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
    10. 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
    11. Simon Döring and Daniel Neuen. The Classical Weisfeiler-Leman Algorithm Stabilizes in O(n)O(n) 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.

    Loading discussion…