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 \({\widetilde{O}}({\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).