Moritz Lichter

"Walk refinement, walk logic, and the iteration number of the Weisfeiler-Leman algorithm"

The Weisfeiler-Leman algorithm is a combinatorical algorithm on graphs that can be used to test graphs for non-isomorphism. It is employed as subroutine in Babai's quasipolynomial time algorithms for graph isomorphism, which makes graph isomorphism one of the rare candidates for NP intermediate problems. Beyond that, there is a strong connection between the Weisfeiler-Leman algorithm, a certain logic, and an associated game played on graphs. The algorithm continues to apply a refinement routine, the so-called Weisfeiler-Leman refinement, to a graph until this process stabilizes. In this talk I will present results to appear at LICS '19 regarding the classical, 2-dimensional, Weisfeiler-Leman refinement: We show that the classical Weisfeiler-Leman algorithm stabilizes n-vertex graphs after at most O(n*log(n)) iterations reaching the best known lower bound of Ω(n) up to a logarithmic factor. This implies that formulas of quantifier depth O(n*log(n)) suffice to distinguish two graphs in 3-variable first order logic with counting (given that the graphs are distinguishable at all). For this we exploit a new refinement based on counting walks and argue that its iteration number differs from the classic Weisfeiler-Leman refinement by at most a logarithmic factor. We then prove matching linear upper and lower bounds on the number of iterations of the walk refinement. This is achieved with an algebraic approach by exploiting properties of semisimple matrix algebras. (joined work with Ilia Ponomarenko and Pascal Schweitzer).