<p>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?</p>

CC BY-SA 3.0
2015-12-14T00:16:37.837Z
By "rank of a graph" do you mean the rank of the adjacency matrix over $\mathbb{R}$? $\mathbb{F}_2$? Something else?
Joshua Grochow
CC BY-SA 3.0
2015-12-14T01:26:58.690Z
@JoshuaGrochow over $\Bbb R$?
Turbo
CC BY-SA 3.0
2015-12-14T02:02:13.597Z
@JoshuaGrochow do you also know if GI is random self reducible in some sense like Discrete Log http://cstheory.stackexchange.com/questions/33274/are-graph-and-group-isomorphism-problems-random-self-reducible? the issue is GI seems easy on most graph classes unlike dlog and so can that post be salvaged?
Turbo
<graph-isomorphism>
On low rank graph isomorphism
Turbo
# On low rank graph isomorphism

(Asked by: username_0 on 2015-12-13)

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?

**Tags:** graph-isomorphism

> **Comments:**
> **username_1**: By "rank of a graph" do you mean the rank of the adjacency matrix over $\mathbb{R}$? $\mathbb{F}_2$? Something else?  
> **username_0**: @JoshuaGrochow over $\Bbb R$?  
> **username_0**: @JoshuaGrochow do you also know if GI is random self reducible in some sense like Discrete Log http://cstheory.stackexchange.com/questions/33274/are-graph-and-group-isomorphism-problems-random-self-reducible? the issue is GI seems easy on most graph classes unlike dlog and so can that post be salvaged?  

---

## 0 answers

