TR08-040 Authors: Sourav Chakraborty, Laszlo Babai

Publication: 8th April 2008 09:58

Downloads: 3392

Keywords:

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.