  The combinatorial refinement techniques have proven to be an efficient
approach to isomorphism testing for particular classes of graphs. If the number
of refinement rounds is small, this puts the corresponding isomorphism problem
in a low-complexity class. We investigate the round complexity of the
2-dimensional Weisfeiler-Leman algorithm on circulant graphs, i.e. on Cayley
graphs of the cyclic group $\mathbb{Z}_n$, and prove that the number of rounds
until stabilization is bounded by $\mathcal{O}(d(n)\log n)$, where $d(n)$ is
the number of divisors of $n$. As a particular consequence, isomorphism can be
tested in NC for connected circulant graphs of order $p^\ell$ with $p$ an odd
prime, $\ell>3$ and vertex degree $\Delta$ smaller than $p$.
  We also show that the color refinement method (also known as the
1-dimensional Weisfeiler-Leman algorithm) computes a canonical labeling for
every non-trivial circulant graph with a prime number of vertices after
individualization of two appropriately chosen vertices. Thus, the canonical
labeling problem for this class of graphs has at most the same complexity as
color refinement, which results in a time bound of $\mathcal{O}(\Delta n\log
n)$. Moreover, this provides a first example where a sophisticated approach to
isomorphism testing put forward by Tinhofer has a real practical meaning.
