<p>If Graph Isomorphism is randomly self-reducible in the sense of the question (clarified in the comments), then it could be solved in poly time. The reason is that there is in fact an average-case <em>linear time</em> algorithm for GI (even a canonical form) [BK].</p>

<p>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...</p>

<p>[BK]. Laszlo Babai, Ludik Kucera, <a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.1979.8" rel="nofollow">Canonical labelling of graphs in linear average time</a>. FOCS 1979, pp.39-46.</p>

CC BY-SA 3.0
2015-12-14T04:36:01.930Z
I suppose even if they turn out to be rsr it will not have effects on other complexity classes?
Turbo
CC BY-SA 3.0
2015-12-14T05:14:27.787Z
That would be my guess, though of course one never knows where unexpected connections can occur...
Joshua Grochow
CC BY-SA 3.0
2015-12-19T09:43:19.807Z
could GI be random self reducible in following sense(1) and/or 2)). 1) For all isomorphism classes for all graph pairs in the same isomorphism class if you can figure out isomorphism for say 1/log(# elements in isomorphism class) in polynomial time then there is a randomized algorithm for graph isomorphism in polynomial time for every graph pair.
Turbo
CC BY-SA 3.0
2015-12-19T09:43:23.123Z
2) For all pairs of isomorphism classes for all graph pairs in the with one member of pair per isomorphism class if you can figure out non-isomorphism for say 1/log(# pairs in the pairs of isomorphism class) in polynomial time then there is a randomized algorithm for graph non-isomorphism in polynomial time for every graph pair.
Turbo
CC BY-SA 3.0
2015-12-14T04:12:41.500Z
2015-12-14T04:12:41.500Z
Joshua Grochow
<p>Are Graph and Group Isomorphism problems known to be random self-reducible? If so is there a good proof?</p>

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

CC BY-SA 3.0
2015-12-06T23:04:09.540Z
What do you mean exactly by "random self-reducible"?
Kaveh
CC BY-SA 3.0
2015-12-06T23:19:08.320Z
@Kaveh Something along lines of Dlog or permanent like in https://en.wikipedia.org/wiki/Random_self-reducibility
Turbo
CC BY-SA 3.0
2015-12-07T01:46:10.307Z
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
CC BY-SA 3.0
2015-12-07T04:12:01.543Z
@SashoNikolov In here https://books.google.com/books?id=jKEEeScADuMC&pg=PA98&lpg=PA98&dq="graph+isomorphism"+"random+self+reducible" it is stated graph isomorphism is random self reducible. What does it mean here?
Turbo
CC BY-SA 3.0
2015-12-07T05:01:53.483Z
It's the notion from this paper http://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
CC BY-SA 3.0
2015-12-14T03:00:03.683Z
I am thinking following. Suppose we have can find isomorphism of pairs ${(G_i,\sigma(G_i))}$ for 1/log(total isomorphic classes) in poly time (with condition that no two of pairs are isomorphic to each other) for any $\sigma\in S_n$ would it be possible to deduce isomorphism between any arbitrary pair (G,H) if one exists and decide not if one does not exist from the polynomially many in list?
Turbo
<cc.complexity-theory><graph-isomorphism><gr.group-theory><average-case-complexity><worst-case>
Are Graph and Group Isomorphism problems random self-reducible?
Turbo
# Are Graph and Group Isomorphism problems random self-reducible?

(Asked by: username_0 on 2015-12-06)

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?

**Tags:** cc.complexity-theory, graph-isomorphism, gr.group-theory, average-case-complexity, worst-case

> **Comments:**
> **username_1**: What do you mean exactly by "random self-reducible"?  
> **username_0**: @username_1 Something along lines of Dlog or permanent like in https://en.wikipedia.org/wiki/Random_self-reducibility  
> **username_2**: 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.)  
> **username_0**: @SashoNikolov In here https://books.google.com/books?id=jKEEeScADuMC&pg=PA98&lpg=PA98&dq="graph+isomorphism"+"random+self+reducible" it is stated graph isomorphism is random self reducible. What does it mean here?  
> **username_2**: It's the notion from this paper http://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*?  
> **username_0**: I am thinking following. Suppose we have can find isomorphism of pairs ${(G_i,\sigma(G_i))}$ for 1/log(total isomorphic classes) in poly time (with condition that no two of pairs are isomorphic to each other) for any $\sigma\in S_n$ would it be possible to deduce isomorphism between any arbitrary pair (G,H) if one exists and decide not if one does not exist from the polynomially many in list?  

---

## 1 answers

### Answer by username_3 on 2015-12-14. Score: 2 | Accepted answer

If Graph Isomorphism is randomly self-reducible in the sense of the question (clarified in the comments), then it could be solved in poly time. The reason is that there is in fact an average-case *linear time* algorithm for GI (even a canonical form) [BK].

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...

[BK]. Laszlo Babai, Ludik Kucera, [Canonical labelling of graphs in linear average time](http://doi.ieeecomputersociety.org/10.1109/SFCS.1979.8). FOCS 1979, pp.39-46.

> **Comments:**
> **username_0**: I suppose even if they turn out to be rsr it will not have effects on other complexity classes?  
> **username_3**: That would be my guess, though of course one never knows where unexpected connections can occur...  
> **username_0**: could GI be random self reducible in following sense(1) and/or 2)). 1) For all isomorphism classes for all graph pairs in the same isomorphism class if you can figure out isomorphism for say 1/log(# elements in isomorphism class) in polynomial time then there is a randomized algorithm for graph isomorphism in polynomial time for every graph pair.  
> **username_0**: 2) For all pairs of isomorphism classes for all graph pairs in the with one member of pair per isomorphism class if you can figure out non-isomorphism for say 1/log(# pairs in the pairs of isomorphism class) in polynomial time then there is a randomized algorithm for graph non-isomorphism in polynomial time for every graph pair.  

---

