-3
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ What do you mean exactly by "random self-reducible"? $\endgroup$ – Kaveh Dec 6 '15 at 23:04
  • $\begingroup$ @Kaveh Something along lines of Dlog or permanent like in en.wikipedia.org/wiki/Random_self-reducibility $\endgroup$ – T.... Dec 6 '15 at 23:19
  • 3
    $\begingroup$ 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.) $\endgroup$ – Sasho Nikolov Dec 7 '15 at 1:46
  • $\begingroup$ @SashoNikolov In here books.google.com/…" it is stated graph isomorphism is random self reducible. What does it mean here? $\endgroup$ – T.... Dec 7 '15 at 4:12
  • 3
    $\begingroup$ 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? $\endgroup$ – Sasho Nikolov Dec 7 '15 at 5:01
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I suppose even if they turn out to be rsr it will not have effects on other complexity classes? $\endgroup$ – T.... Dec 14 '15 at 4:36
  • $\begingroup$ That would be my guess, though of course one never knows where unexpected connections can occur... $\endgroup$ – Joshua Grochow Dec 14 '15 at 5:14
  • $\begingroup$ 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. $\endgroup$ – T.... Dec 19 '15 at 9:43
  • $\begingroup$ 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. $\endgroup$ – T.... Dec 19 '15 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.