On low rank graph isomorphism Is there a $c&gt;1$ (maybe $c=2$) such that every lower than rank $n^{1/c}$ graphs on $n$ vertices can be tested to be in polynomial time?
There is such a c if and only if GI "can be tested to be in polynomial time",

since one can pad with nc isolated vertices.

I don't know of any results on random self reducibility of GI.