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

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

### #1

# [Link] Quasi-Polynomial Time Algorithm for Graph Isomorphism

Posted 04 November 2015 - 09:20 PM

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

### #2

## 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.

### #3

## 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.

### #4

## 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?

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?

### #5

## 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.

### #6

## 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!

### #7

## 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.

### #9

## 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.

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.

### #10

## 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.

### #11

## 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?

what do you guys think?

### #12

## 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.

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.

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

### #13

## 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.

### #14

## 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?

### #15

## 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!