Berkholz's question: is Weisfeiler-Leman equivalence with the dimension as part of the input EXPTIME-complete?

Theorem 1.1 (principal manuscript): deciding joint-update $k$-WL equivalence with $k\ge2$ in binary and explicit adjacency matrices is EXPTIME-complete under polynomial-time many-one reductions, also for connected simple uncoloured graphs of equal order and maximum degree three. Companions claim: deciding whether a given dimension identifies a graph (WL dimension at most $k$) is EXPTIME-complete, also with $k$ in unary; for every large fixed $k$, deciding $k$-WL equivalence needs $n^{\Omega(k)}$ deterministic sequential time unconditionally (multitape Turing machines and log-word RAMs, diameter-two graphs); and parity lifts give $n^{\Omega(k)}$ exclusions under ETH. No randomized or nonuniform lower bounds are claimed, and the separate-update convention is treated only in the fixed-dimension companions.

Theorem 1.1 (principal manuscript): deciding joint-update $k$-WL equivalence with $k\ge2$ in binary and explicit adjacency matrices is EXPTIME-complete under polynomial-time many-one reductions, also for connected simple uncoloured graphs of equal order and maximum degree three. Companions claim: deciding whether a given dimension identifies a graph (WL dimension at most $k$) is EXPTIME-complete, also with $k$ in unary; for every large fixed $k$, deciding $k$-WL equivalence needs $n^{\Omega(k)}$ deterministic sequential time unconditionally (multitape Turing machines and log-word RAMs, diameter-two graphs); and parity lifts give $n^{\Omega(k)}$ exclusions under ETH. No randomized or nonuniform lower bounds are claimed, and the separate-update convention is treated only in the fixed-dimension companions.