[Link] Quasi-Polynomial Time Algorithm for Graph Isomorphism

  • (2 Pages)
  • +
  • 1
  • 2

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

#16 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 17 November 2015 - 03:07 PM

They released the video recording: http://people.cs.uch...5-11-10talk.mp4
Was This Post Helpful? 1
  • +
  • -

#17 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12135
  • View blog
  • Posts: 45,119
  • Joined: 27-December 08

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.
Was This Post Helpful? 0
  • +
  • -

#18 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12135
  • View blog
  • Posts: 45,119
  • Joined: 27-December 08

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

Posted 19 December 2015 - 02:53 PM

Babai has published his paper:

http://arxiv.org/pdf/1512.03547v1.pdf
Was This Post Helpful? 1
  • +
  • -

#19 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 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?
Was This Post Helpful? 0
  • +
  • -

#20 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 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.
Was This Post Helpful? 0
  • +
  • -

#21 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12135
  • View blog
  • Posts: 45,119
  • Joined: 27-December 08

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

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.
Was This Post Helpful? 0
  • +
  • -

#22 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 13400
  • View blog
  • Posts: 53,479
  • Joined: 12-June 08

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!
Was This Post Helpful? 0
  • +
  • -

#23 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 5828
  • View blog
  • Posts: 19,868
  • Joined: 05-May 12

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?
Was This Post Helpful? 0
  • +
  • -

#24 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12135
  • View blog
  • Posts: 45,119
  • Joined: 27-December 08

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

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.

Was This Post Helpful? 1
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2