Graph Isomorphism is in SPP

We show that Graph Isomorphism is in the complexity class SPP, and hence it is in ⊕P (in fact, in Mod_kP for each k ? 2). These inclusions for Graph Isomorphism were not known prior to membership in SPP. 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 ? 2.