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?
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.
External links referenced by this document: