Lower Bounds for the Weisfeiler-Leman Algorithm via Implicit Parity SystemsResearch Paper
The -dimensional Weisfeiler–Leman algorithm (-WL) is the central combinatorial heuristic for graph isomorphism. It refines a coloring of -tuples of vertices round by round, and two graphs are told apart when their color statistics differ. The number of rounds is a natural measure in several fields: it equals the quantifier depth in the logic with…