The computational complexity of Weisfeiler–Leman refinement

What OpenAI claims

Proves unconditional n^Ω(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. (Lean)

Papers (4)

1. Parity lifts and bounded-treewidth witnesses for Weisfeiler–Leman equivalence

   25 September 2026 · Preprint, not peer reviewed · PDF

   For k ≥ 4, we construct two uncolored graphs that are k-dimensional Weisfeiler–Leman equivalent exactly when a prescribed finite-domain choice system has no compatible choice. The system has k+1 domains for joint refinement and k for separate-coordinate refinement. A successful choice is detected after two joint rounds or one separate round. Applied to sparse satisfiability, the reduction gives fixed-dimension n^Ω(k) time exclusions under positive-rate ETH, even for deciding equality of these early histograms.

2. The complexity of identifying a graph by Weisfeiler–Leman refinement

   25 September 2026 · Preprint, not peer reviewed · PDF

   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.

3. Unconditional time lower bounds for Weisfeiler–Leman equivalence

   25 September 2026 · Preprint, not peer reviewed · PDF

   For every sufficiently large fixed k, deciding whether two n-vertex graphs are k-Weisfeiler–Leman equivalent requires n^Ω(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.

4. Variable-dimension Weisfeiler–Leman equivalence on general and subcubic graphs

   25 September 2026 · Preprint, not peer reviewed · PDF

   Deciding joint-update k-dimensional Weisfeiler–Leman equivalence is EXPTIME-complete when the two graphs are given by explicit adjacency matrices and k ≥ 2 is encoded in binary. The result holds even for connected simple uncolored graphs of equal positive order and maximum degree at most three.

Status

Preprint. The papers have not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.