mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Combinatorics & Combinatorial Number Theory (https://www.mersenneforum.org/forumdisplay.php?f=112)
-   -   Combinatorics news (https://www.mersenneforum.org/showthread.php?t=20628)

Nick 2015-11-06 09:11

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/a-big-result-on-graph-isomorphism/[/URL]

CRGreathouse 2015-11-10 21:06

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?

jwaltos 2015-11-11 04:43

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 [U]integer factorization[/U]. It is however known that if the problem is NP-complete then the polynomial hierarchy collapses to a finite level.[3]"

Nick 2015-11-11 19:08

[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/babai-s-first-graph-isomorphism-talk[/URL]

danaj 2015-11-12 16:27

A little more info:

[url]http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/[/url]

only_human 2015-11-17 06:55

[QUOTE=danaj;415937]A little more info:

[url]http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/[/url][/QUOTE]
Jeremy Kun adds:
[QUOTE]Update 2015-11-16: Laci has [URL="http://people.cs.uchicago.edu/~laci/2015-11-10talk.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 more-or-less completed in the early 1980s. To my mind, this raises a fascinating socio-mathematical 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 third-of-a-century 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]

Nick 2017-01-10 12:44

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

Nick 2019-12-14 15:25

New open journal:
[URL]https://www.advancesincombinatorics.com/[/URL]


All times are UTC. The time now is 13:46.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.