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=3Dr(n)$ such that the ``$r$-neighborhoods'' of the $n$ different vertices are pairwise non-isomorphic).