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?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ By "rank of a graph" do you mean the rank of the adjacency matrix over $\mathbb{R}$? $\mathbb{F}_2$? Something else? $\endgroup$– Joshua GrochowDec 14, 2015 at 0:16
-
$\begingroup$ @JoshuaGrochow over $\Bbb R$? $\endgroup$– TurboDec 14, 2015 at 1:26
-
$\begingroup$ @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? $\endgroup$– TurboDec 14, 2015 at 2:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
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.
-
$\begingroup$ What is the consequence if GI is in BPP, RP, coRP or ZPP? Is it known to be any of these classes already? $\endgroup$– TurboDec 14, 2015 at 2:56
-
2$\begingroup$ @Turbo: It is not known. As far as I know, the main consequence of GI being in any of those classes would just be that GI is in that class... As a meta-remark, Turbo, you seem to be recently asking lots of fairly easy questions indicating that you are learning about Boolean complexity (coming, it would seem, from the algebraic world, where your questions are generally much more sophisticated). I would recommend that, in addition to the usual textbooks and exercises, that you read the book on GI by Kobler, Schoning, and Toran. It is a nice read and I think you will get a lot out of it. $\endgroup$ Dec 14, 2015 at 4:02
-
2$\begingroup$ @Turbo : By the search-to-decision reduction for GI (Example B.6 on pages 356 and 357 (see "Back Matter") of "Universal Semantic Communication" by Brendan Juba; google books has page 356), if GI is in BPP then GI is in RP. As a consequence of that, if GI is in coRP then GI is in ZPP. $\endgroup$– user6973Dec 14, 2015 at 6:50
-
$\begingroup$ @RickyDemer Is it possible that it is sufficient to show full rank GI is in P for general GI to be in P or is there a possibility that full rank GI could be in P while lower rank GI is not in P? is there any implication? $\endgroup$– TurboDec 21, 2015 at 9:45
-
$\begingroup$ @Turbo : I'm not aware of any such implication. $\endgroup$– user6973Dec 21, 2015 at 9:48