Theoretical Computer Science
cc.complexity-theory graph-isomorphism gr.group-theory average-case-complexity worst-case
Updated Mon, 20 Jun 2022 12:03:13 GMT

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?

Solution

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. FOCS 1979, pp.39-46.

Comments (4)

  • +0 – I suppose even if they turn out to be rsr it will not have effects on other complexity classes? — Dec 14, 2015 at 04:36  
  • +0 – That would be my guess, though of course one never knows where unexpected connections can occur... — Dec 14, 2015 at 05:14  
  • +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. — Dec 19, 2015 at 09:43  
  • +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. — Dec 19, 2015 at 09:43  

External Links

External links referenced by this document:

References