__
Revision #1 to TR23-146 | 27th November 2023 13:49
__
#### On Testing Isomorphism to a Fixed Graph in the Bounded-Degree Graph Model

**Abstract:**
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).

**Changes to previous version:**
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.

__
TR23-146 | 27th September 2023 15:45
__

#### On Testing Isomorphism to a Fixed Graph in the Bounded-Degree Graph Model

**Abstract:**
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).