20151106, 09:11  #1 
Dec 2012
The Netherlands
2×859 Posts 
Combinatorics news
Laszlo Babai has apparently found a new algorithm solving the graph isomorphism problem in quasipolynomial time.
University of Chicago talks (10 and 24 November 2015): http://www.math.uchicago.edu/calenda...uter%20Science Some background: https://rjlipton.wordpress.com/2015/...hisomorphism/ 
20151110, 21:06  #2 
Aug 2006
3·1,993 Posts 
Has anyone heard more about this? I saw the announcement on Scott Aaronson's blog but no details yet. Any reports from today's talk?

20151111, 04:43  #3 
Apr 2012
Brady
389 Posts 
Heard about it and now waiting for analyses from the experts. Am pasting a paragraph from Wiki for background.
"The graph isomorphism problem is one of few standard problems in computational complexity theory belonging to NP, but not known to belong to either of its wellknown (and, if P ≠ NP, disjoint) subsets: P and NPcomplete. It is one of only two, out of 12 total, problems listed in Garey & Johnson (1979) whose complexity remains unresolved, the other being integer factorization. It is however known that if the problem is NPcomplete then the polynomial hierarchy collapses to a finite level.[3]" Last fiddled with by jwaltos on 20151111 at 04:48 
20151111, 19:08  #4  
Dec 2012
The Netherlands
2·859 Posts 
Quote:
https://storify.com/ptwiddle/babais...omorphismtalk 

20151112, 16:27  #5 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
909_{10} Posts 

20151117, 06:55  #6  
"Gang aft agley"
Sep 2002
2·1,877 Posts 
Quote:
Quote:
Scott Aaronson said something interesting: http://www.scottaaronson.com/blog/ Quote:


20170110, 12:44  #7 
Dec 2012
The Netherlands
2·859 Posts 
Update from Babai:
http://people.cs.uchicago.edu/~laci/update.html 
20191214, 15:25  #8 
Dec 2012
The Netherlands
3266_{8} Posts 
New open journal:
https://www.advancesincombinatorics.com/ 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Stacking boxes  combinatorics?  Ken_g6  Puzzles  15  20100804 23:30 
Other news  Cruelty  Riesel Prime Search  41  20100308 18:46 
The news giveth, the news taketh away...  NBtarheel_33  Hardware  17  20090504 15:52 
News  KEP  Riesel Base 3 Attack  4  20081217 11:54 
Combinatorics  Kees  Puzzles  6  20060513 06:58 