Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-146 | 27th November 2023 13:49

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

RSS-Feed




Revision #1
Authors: Oded Goldreich, Laliv Tauber
Accepted on: 27th November 2023 13:49
Downloads: 3
Keywords: 


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.


Paper:

TR23-146 | 27th September 2023 15:45

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





TR23-146
Authors: Oded Goldreich, Laliv Tauber
Publication: 27th September 2023 15:47
Downloads: 141
Keywords: 


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).



ISSN 1433-8092 | Imprint