[Link] Quasi-Polynomial Time Algorithm for Graph Isomorphism

  • (2 Pages)
  • +
  • 1
  • 2

23 Replies - 6660 Views - Last Post: 11 January 2017 - 01:45 PM

#1 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,114
  • Joined: 27-December 08

[Link] Quasi-Polynomial Time Algorithm for Graph Isomorphism

Post icon  Posted 04 November 2015 - 09:20 PM

Laszlo Babai at the University of Chicago claims to have a quasi polynomial time (exp(polylog(n)) time) algorithm to decide if two graphs are isomorphic. If his claims are true (and they likely are), then this is the complexity result of the decade. The best known algorithm thus far is exp( sqrt(n log n)) time. Babai is presenting his results on Tuesday at a seminar at the University of Chicago.

Graph Isomorphism is believed to be NP-Intermediate. That is, if P and NP are different sets, then GI lies in NP (which we already know to be true) but is neither P nor NP-Complete. In contrast, Subgraph Isomorphism (given graphs G and H, is H a subgraph of G?) is NP-Complete.

https://news.ycombin...tem?id=10505231

Is This A Good Question/Topic? 2
  • +

Replies To: [Link] Quasi-Polynomial Time Algorithm for Graph Isomorphism

#2 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

Re: [Link] Quasi-Polynomial Time Algorithm for Graph Isomorphism

Posted 04 November 2015 - 11:28 PM

This is so awesome! I really really hope the constant is small enough to be practical. I'm sure there are tons of applications for this.
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,114
  • Joined: 27-December 08

Re: [Link] Quasi-Polynomial Time Algorithm for Graph Isomorphism

Posted 06 November 2015 - 09:40 PM

I emailed the coordinator of the Theory of Computation/Combinatorics seminar at Chicago to ask if the talks would be streamed. They will not, per Babai's request. However, they will be videoed, and the videos will be made public at a later date.
Was This Post Helpful? 0
  • +
  • -

#4 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

Re: [Link] Quasi-Polynomial Time Algorithm for Graph Isomorphism

Posted 08 November 2015 - 09:12 PM

So what do we know about this?

We know that the algorithm is some kind of divide and conquer and based around group theory.
We know "Schreier's hypothesis" will be used whatever that is
I saw it speculated that the classification of finite simple groups was going to play a role (which would explain why this was such a hard result if such a big gun had to be used)
We can guess some kind of certificate will be used for sub parts based on the term "local certificates" which probably means that these are certificates being used for building a bigger certificate out of the sub parts

Anything else?
Was This Post Helpful? 0
  • +
  • -

#5 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

Re: [Link] Quasi-Polynomial Time Algorithm for Graph Isomorphism

Posted 11 November 2015 - 06:36 PM

here is a reddit link from a guy that seems to have been at the talk. It doesn't really tell us too much but I'm eager to see more. Hopefully we will see more next week.
Was This Post Helpful? 1
  • +
  • -

#6 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,114
  • Joined: 27-December 08

Re: [Link] Quasi-Polynomial Time Algorithm for Graph Isomorphism

Posted 11 November 2015 - 07:28 PM

Actually it will be the following week Babai speaks again about this. Good find though!
Was This Post Helpful? 0
  • +
  • -

#7 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

Re: [Link] Quasi-Polynomial Time Algorithm for Graph Isomorphism

Posted 12 November 2015 - 01:42 AM

Yea I just meant hopefully more people will crack down and give us the goods. Understandably Laszlo wants this to be peer reviewed before misinformation possibly gets out so he is keeping things under wraps until then (and has apparently asked people not to talk about the result). Since some people have already started to leak a bit of info however I'm eager to hear more leaked info.
Was This Post Helpful? 0
  • +
  • -

#8 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

Re: [Link] Quasi-Polynomial Time Algorithm for Graph Isomorphism

Posted 12 November 2015 - 02:35 PM

here is a much more informative link. I haven't made it though my self but I figured I'd post it for others while I'm working my way though it.
Was This Post Helpful? 1
  • +
  • -

#9 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,114
  • Joined: 27-December 08

Re: [Link] Quasi-Polynomial Time Algorithm for Graph Isomorphism

Posted 12 November 2015 - 03:06 PM

Nice find, ishkabible!

For those interested and not already familiar with the material, I have some blog entries on graph automorphisms. Some basic group theoretic techniques are illustrated. This might help those without an algebra background get up to speed.
Was This Post Helpful? 0
  • +
  • -

#10 tarmizi_adam2005  Icon User is offline

  • جوروترا

Reputation: 287
  • View blog
  • Posts: 984
  • Joined: 18-April 09

Re: [Link] Quasi-Polynomial Time Algorithm for Graph Isomorphism

Posted 12 November 2015 - 11:41 PM

As an engineer, I'm just curious on what is the application of this in science and engineering ? This looks like some breakthrough in mathematics/theoretical computer science, but my math background is not up this level. :dontgetit:
Was This Post Helpful? 0
  • +
  • -

#11 CodeCruncher  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • Posts: 10
  • Joined: 02-December 12

Re: [Link] Quasi-Polynomial Time Algorithm for Graph Isomorphism

Posted 14 November 2015 - 12:33 AM

Scott Aaronson said it is potentially along the lines of "its the biggest computer science achievement of the decade"

what do you guys think?
Was This Post Helpful? 0
  • +
  • -

#12 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

Re: [Link] Quasi-Polynomial Time Algorithm for Graph Isomorphism

Posted 14 November 2015 - 02:05 AM

If Laszlo is right he might get the Turing award for it. Given his already huge contributions to complexity theory it wouldn't be uncalled for.

Additionally this might lead to either proving that Graph Isomorphism is in P or that it is not. If it is proven that, as Laszlo expects, that GI is not in P then we have our proof of P!=NP. If it is in P then that is another nail in the coffin for NP-intermediate problems (which we desperately want to find in order to prove P!=NP). The proof of GI not being in P, if it exists, is probably extremely hard to find but some progress was made here. Apparently certain combinatorics were learned about the problem that seem to very strongly suggest that GI is not in P. I don't know all of the details and you should take what I am saying with a huge grain of salt mind you. What I'm telling you is a) not per-reviewed b) I've heard this though the grapevine and c) I don't really know this material. All that withholding it sounds to me like some progress might have been made towards PvsNP. Historically when someone has found a quasi-polynomal algorithm a polynomial algorithm was just around the corner. This one might be special however. That said proving it is special is likely an order of magnitude harder to prove.

Quote

As an engineer, I'm just curious on what is the application of this in science and engineering ? This looks like some breakthrough in mathematics/theoretical computer science, but my math background is not up this level.

I was reading about all the things GI is used in but we already have good heuristics for those cases and supposedly (again I don't have direct sources) Laszlo isn't to hopeful his proof will lead to an implementation. This might just be of theoretical interest albeit extreme theoretical.

This post has been edited by ishkabible: 14 November 2015 - 02:33 AM

Was This Post Helpful? 0
  • +
  • -

#13 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,114
  • Joined: 27-December 08

Re: [Link] Quasi-Polynomial Time Algorithm for Graph Isomorphism

Posted 14 November 2015 - 08:12 AM

GI is already known to be in NP. So we only have a proof that P != NP is in NP if we show that GI is in P but not NP-Complete.
Was This Post Helpful? 0
  • +
  • -

#14 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

Re: [Link] Quasi-Polynomial Time Algorithm for Graph Isomorphism

Posted 15 November 2015 - 03:09 AM

Perhaps I'm not understanding something. We know that GI is in NP. If we prove that GI is not in P then we have a problem which is in NP and not in P. So we have a proof of P!=NP because there is a problem that they don't share. Proving that GI isn't NP-complete is irrelevant isn't it?
Was This Post Helpful? 0
  • +
  • -

#15 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,114
  • Joined: 27-December 08

Re: [Link] Quasi-Polynomial Time Algorithm for Graph Isomorphism

Posted 15 November 2015 - 05:33 AM

You would be correct. I was not thinking in my last response!
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2