Combinatorics news

[Nick]

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/...h-isomorphism/

[CRGreathouse]

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 well-known (and, if P ≠ NP, disjoint) subsets: P and NP-complete. 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 NP-complete then the polynomial hierarchy collapses to a finite level.[3]"

[Nick]

Originally Posted by CRGreathouse

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?

No paper yet, but here is an account from someone at the first talk:

https://storify.com/ptwiddle/babai-s...omorphism-talk

[danaj]

A little more info:

http://jeremykun.com/2015/11/12/a-qu...m-the-details/

[only_human]

Originally Posted by danaj

A little more info:

http://jeremykun.com/2015/11/12/a-qu...m-the-details/

Jeremy Kun adds:

Update 2015-11-16: Laci has posted the talk on his website. It’s an hour and a half long, and I encourage you to watch it if you have the time

also,
Scott Aaronson said something interesting:
http://www.scottaaronson.com/blog/

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 more-or-less completed in the early 1980s. To my mind, this raises a fascinating socio-mathematical question: 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? 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 third-of-a-century break between his and Luks’ work in the early 80s, and the “natural next step” in their program … and still no one managed to use that break to beat him to the next step!

[Nick]

Update from Babai:
http://people.cs.uchicago.edu/~laci/update.html

[Nick]

New open journal:
https://www.advancesincombinatorics.com/