**Authors:** V. Arvind, Richard Beigel, and Antoni Lozano

**Abstract:**
Motivated by the question of the relative complexities of the Graph
Isomorphism and the Graph Automorphism problems, we define and study
the modular graph automorphism problems. These are the decision
problems MOD_{k}GA which consist, for each *k*
> 1, of deciding whether the number of automorphisms of a graph is
divisible by *k*. The MOD_{k}GA problems all turn
out to be intermediate in difficulty between Graph Automorphism and
Graph Isomorphism.

We define an appropriate search version of MOD_{k}GA
and design an algorithm that polynomial-time reduces the
MOD_{k}GA search problem to the decision problem.
Combining this algorithm with an IP protocol, we obtain a randomized
polynomial-time checker for MOD_{k}GA, for all
*k* > 1