# Are Graph and Group Isomorphism problems random self-reducible?

Are Graph and Group Isomorphism problems known to be random self-reducible? If so is there a good proof?

Are there other non-trivial examples of random self-reducibility? Is there a good reference?

• What do you mean exactly by "random self-reducible"? – Kaveh Dec 6 '15 at 23:04
• @Kaveh Something along lines of Dlog or permanent like in en.wikipedia.org/wiki/Random_self-reducibility – T.... Dec 6 '15 at 23:19
• So you want to reduce the problem of deciding if graph $G$ is isomorphic to $H$ to deciding isomorphism on $m = \textrm{poly}(n)$ pairs $(G_1, H_2), \ldots, (G_m, H_m)$ where each $(G_i, H_i)$ is distributed uniformly over all pairs of graphs on n vertices? This makes little sense since a uniformly distributed pair of graphs is non-isomorphic with very high probability. Do you mean something else? (As has been pointed out before, you should think harder before asking questions.) – Sasho Nikolov Dec 7 '15 at 1:46
• @SashoNikolov In here books.google.com/…" it is stated graph isomorphism is random self reducible. What does it mean here? – T.... Dec 7 '15 at 4:12
• It's the notion from this paper dx.doi.org/10.1109/SFCS.1987.49. The reduction takes $(G, H)$ and outputs $(G, H')$, where $H'$ is $H$ with the vertices uniformly permuted. This reduces GI to distinguishing between the cases (1) $H$ is a uniform graph from the isomorphism class of $G$; (2) $G$ and $H$ are not isomorphic. But this is not a reduction to uniform instances of GI. The question is, what notion of random self-reducability do you want, precisely? – Sasho Nikolov Dec 7 '15 at 5:01

For Group Isomorphism, this is not known. However, it's also somewhat of a funny question, because of how much the group order can restrict the structure of a group. In many senses, most groups are of order $2^k$, and are nilpotent of class 2. I find it hard to see how one would get a random self-reduction for GroupIso...