We show that Graph Isomorphism is in the complexity class SPP, and hence it is in \oplusP (in fact, it is in Mod_kP for each k \geqslant 2). We derive this result as a corollary of a more general result: we show that a generic problem FIND-GROUP has an FP^SPP algorithm.

This general result has other consequences: for example, it follows that the hidden subgroup problem for permutation groups, studied in the context of quantum algorithms, has an FP^SPP algorithm. Also, some other algorithmic problems over permutation groups known to be at least as hard as Graph Isomorphism (e.g. coset intersection) are in SPP, and thus in Mod_kP for each k \geqslant 2.