For a permutation group $G$ acting on the set $\Omega$
we say that two strings $x,y\,:\,\Omega\to\boole$
are {\em $G$-isomorphic} if they are equivalent under
the action of $G$, \ie, if for some $\pi\in G$ we have
$x(i^{\pi})=y(i)$ for all $i\in\Omega$.
Cyclic Shift, Graph Isomorphism and Hypergraph Isomorphism
are special cases, and subcases corresponding to certain
classes of groups have been central to the design of efficient
isomorphism testing for subclasses of graphs (Luks 1982).
We study the complexity of $G$-isomorphism in the context of property
testing: we want to find the randomized decision tree complexity
of distinguishing
the cases when $x$ and $y$ are $G$-isomorphic from the cases when
they are at least $\delta$-far from being $G$-isomorphic
(in normalized Hamming distance). Error can be 1-sided or
2-sided.
In each case we consider two models. In
the query-1 model we assume $y$ is known and
only $x$ needs to be queried.
In the query-2 model we have to query both $x$ and $y$.
We give various upper and lower bounds for the four combinations
of models considered in terms of $n=|\Omega|$ and $|G|$.
In many cases, substantial gaps remain
between the upper and lower bounds. However, for {\em primitive
permutation groups}, we obtain
a tight (up to polylog($n$) factors) bound of
$\wti{\Theta}(\sqrt{n\log |G|})$ for
the 1-sided error query complexity in the query-2 model and a tight
bound of $\wti{\Theta}(\log |G|)$ for the 1-sided error query complexity
in the query-1 model.
This result extends results of Fischer and
Matsliah (2006) on Graph Isomorphism
to a surprisingly general class of groups which also includes
isomorphism of uniform hypergraphs of any rank. Besides the
fact that they include Graph Isomorphism,
primitive permutation groups are significant because they
form the ``building blocks'' of all permutations groups,
providing the base cases of a natural divide-and-conquer
approach successfully exploited in algorithm design (Luks, 1982).
While all our bounds are in terms of the order of $G$, it
seems likely that tighter bounds will depend on the finer
structure of $G$; our result on primitive groups is a first step
in this direction.
