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$ By "rank of a graph" do you mean the rank of the adjacency matrix over $\mathbb{R}$? $\mathbb{F}_2$? Something else? $\endgroup$ – Joshua Grochow Dec 14 '15 at 0:16
  • $\begingroup$ @JoshuaGrochow over $\Bbb R$? $\endgroup$ – 1.. Dec 14 '15 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$ – 1.. Dec 14 '15 at 2:02

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$ – 1.. Dec 14 '15 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$ – Joshua Grochow Dec 14 '15 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$ – user6973 Dec 14 '15 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$ – 1.. Dec 21 '15 at 9:45
  • $\begingroup$ @Turbo : ​ I'm not aware of any such implication. ​ ​ ​ ​ $\endgroup$ – user6973 Dec 21 '15 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.