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): [URL]http://www.math.uchicago.edu/calendar?calendar=Combinatorics%20and%20Theoretical%20Computer%20Science[/URL] Some background: [URL]https://rjlipton.wordpress.com/2015/11/04/abigresultongraphisomorphism/[/URL] 
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?

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 [U]integer factorization[/U]. It is however known that if the problem is NPcomplete then the polynomial hierarchy collapses to a finite level.[3]" 
[QUOTE=CRGreathouse;415731]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?[/QUOTE]
No paper yet, but here is an account from someone at the first talk: [URL]https://storify.com/ptwiddle/babaisfirstgraphisomorphismtalk[/URL] 
A little more info:
[url]http://jeremykun.com/2015/11/12/aquasipolynomialtimealgorithmforgraphisomorphismthedetails/[/url] 
[QUOTE=danaj;415937]A little more info:
[url]http://jeremykun.com/2015/11/12/aquasipolynomialtimealgorithmforgraphisomorphismthedetails/[/url][/QUOTE] Jeremy Kun adds: [QUOTE]Update 20151116: Laci has [URL="http://people.cs.uchicago.edu/~laci/20151110talk.mp4"]posted the talk on his website[/URL]. It’s an hour and a half long, and I encourage you to watch it if you have the time [/QUOTE] also, Scott Aaronson said something interesting: [url]http://www.scottaaronson.com/blog/[/url] [QUOTE]Babai stressed that in some sense, his new algorithm is the culmination of a program laid out by Eugene Luks in 1982. Now, the Classification of Finite Simple Groups was also moreorless completed in the early 1980s. To my mind, this raises a fascinating sociomathematical question: [B]which aspects of the new work, if any, could not have been done in the early 80s, possibly by Babai or Luks themselves? what is it that needed another 30 years?[/B] If the answer turns out to be “nothing,” then to me that’s an astounding illustration of the role of the individual in mathematical progress. As in: Laci was nice enough to take a thirdofacentury break between his and Luks’ work in the early 80s, and the “natural next step” in their program … and [I]still[/I] no one managed to use that break to beat him to the next step![/QUOTE] 
Update from Babai:
[URL]http://people.cs.uchicago.edu/~laci/update.html[/URL] 
New open journal:
[URL]https://www.advancesincombinatorics.com/[/URL] 
All times are UTC. The time now is 05:58. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2022, Jelsoft Enterprises Ltd.