We consider the problem of testing isomorphism to a fixed graph in the bounded-degree graph model. Our main result is that, for almost all $d$-regular $n$-vertex graphs $H$,
testing isomorphism to $H$ can be done using $\tildeO({\sqrt n})$ queries.
This result is shown to be optimal (up to a polylog factor) by a matching lower bound, which also holds for almost all graphs $H$.

The performance of our tester depends on natural graph parameters of the fixed ($n$-vertex) graph $H$ such as its diameter and the minimum radius of ``distinguishing neighborhoods'' (i.e., the minimum $r=r(n)$ such that the ``$r$-neighborhoods'' of the $n$ different vertices are pairwise non-isomorphic).

We discovered that Lemma 2.1 was previously proved by Mossel and Sun, and revised the paper accoringly; that is, omitted our own proof sketch of Lemma 2.1.

We consider the problem of testing isomorphism to a fixed graph in the bounded-degree graph model. Our main result is that, for almost all $d$-regular $n$-vertex graphs $H$,
testing isomorphism to $H$ can be done using $\tildeO({\sqrt n})$ queries.
This result is shown to be optimal (up to a polylog factor) by a matching lower bound, which also holds for almost all graphs $H$.

The performance of our tester depends on natural graph parameters of the fixed ($n$-vertex) graph $H$ such as its diameter and the minimum radius of ``distinguishing neighborhoods'' (i.e., the minimum $r=r(n)$ such that the ``$r$-neighborhoods'' of the $n$ different vertices are pairwise non-isomorphic).