They released the video recording: http://people.cs.uch...5-11-10talk.mp4

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

### #16

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

Posted 17 November 2015 - 03:07 PM

### #17

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

Posted 17 November 2015 - 03:19 PM

That's exciting! I'll have to watch it over the weekend or break next week.

### #18

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

Posted 19 December 2015 - 02:53 PM

### #19

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

Posted 05 January 2016 - 02:58 PM

so what is the consensus of this

i assume its still under review and will be for a long time?

i assume its still under review and will be for a long time?

### #20

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

Posted 08 January 2016 - 07:40 AM

It is still under review as far as I am aware. I'll try to mention when it is published in a journal but I'm not sure which journal he submitted it to and I'm not sure I'll actually be alerted when it is published.

### #21

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

Posted 04 January 2017 - 01:35 PM

Babai retracts claim that GI is quasi-polynomial time and replaces it with subexponential time claim. His algorithm is still the first subexponential GI algorithm, and it is still substantially better than Luks' algorithm in 1983. Babai's algorithm runs in exp(n^{0.01}) time while Luks' algorithm runs in exp(n^{0.5}) time.

From Babai's site: http://people.cs.uch...aci/update.html

I for one am not but so disappointed.

From Babai's site: http://people.cs.uch...aci/update.html

Quote

I apologize to those who were drawn to my lectures on this subject solely because of the quasipolynomial claim, prematurely magnified on the internet in spite of my disclaimers. I believe those looking for an interesting combination of group theory, combinatorics, and algorithms need not feel disappointed.

I for one am not but so disappointed.

### #22

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

Posted 04 January 2017 - 01:35 PM

Time to get pitchforks at the bulk discount store!

### #23

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

Posted 11 January 2017 - 12:12 PM

Maybe I'm missing something, but are both exp(n^{0.01}) and exp(n^{0.5}) subexponential?

### #24

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

Posted 11 January 2017 - 01:45 PM

The Big-O bound is still valid. Subexponential means that the algorithm runs faster than O(n^{\epsilon}) for all \epsilon > 0. Babai explains this more in his update.

Also, Babai has updated his algorithm and reinstated the quasipolynomial claim!

http://people.cs.uch...aci/update.html

Also, Babai has updated his algorithm and reinstated the quasipolynomial claim!

http://people.cs.uch...aci/update.html

Quote

On January 4 I announced that Harald Helfgott pointed out an error in the analysis of my Graph Isomorphism test. The error invalidated my previous claim of quasipolynomial efficiency. The text of the announcement is appended below.

On January 7 I discovered a replacement for the recursive call in the "Split-or-Johnson" routine that had caused the problem. With this modification, I claim that the Graph Isomorphism test runs in quasipolynomial time (now really).

The replacement consists of a few lines of pseudocode, analyzed via a simple new lemma on the structure of coherent configurations.

I am working on an updated arXiv posting.

On January 7 I discovered a replacement for the recursive call in the "Split-or-Johnson" routine that had caused the problem. With this modification, I claim that the Graph Isomorphism test runs in quasipolynomial time (now really).

The replacement consists of a few lines of pseudocode, analyzed via a simple new lemma on the structure of coherent configurations.

I am working on an updated arXiv posting.