  The $k$-dimensional Weisfeiler-Leman ($k$-WL) algorithm is a simple
combinatorial algorithm that was originally designed as a graph isomorphism
heuristic. It naturally finds applications in Babai's quasipolynomial time
isomorphism algorithm, practical isomorphism solvers, and algebraic graph
theory. However, it also has surprising connections to other areas such as
logic, proof complexity, combinatorial optimization, and machine learning.
  The algorithm iteratively computes a coloring of the $k$-tuples of vertices
of a graph. Since F\"urer's linear lower bound [ICALP 2001], it has been an
open question whether there is a super-linear lower bound for the iteration
number for $k$-WL on graphs. We answer this question affirmatively,
establishing an $\Omega(n^{k/2})$-lower bound for all $k$.
