# On low rank graph isomorphism

Is there a $c>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?

• By "rank of a graph" do you mean the rank of the adjacency matrix over $\mathbb{R}$? $\mathbb{F}_2$? Something else? – Joshua Grochow Dec 14 '15 at 0:16
• @JoshuaGrochow over $\Bbb R$? – 1.. Dec 14 '15 at 1:26
• @JoshuaGrochow do you also know if GI is random self reducible in some sense like Discrete Log cstheory.stackexchange.com/questions/33274/…? the issue is GI seems easy on most graph classes unlike dlog and so can that post be salvaged? – 1.. Dec 14 '15 at 2:02