mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Combinatorics & Combinatorial Number Theory

Reply
 
Thread Tools
Old 2015-11-06, 09:11   #1
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

3×11×43 Posts
Default 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/...h-isomorphism/
Nick is offline   Reply With Quote
Old 2015-11-10, 21:06   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×3×977 Posts
Default

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?
CRGreathouse is offline   Reply With Quote
Old 2015-11-11, 04:43   #3
jwaltos
 
jwaltos's Avatar
 
Apr 2012

1010011112 Posts
Default

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]"

Last fiddled with by jwaltos on 2015-11-11 at 04:48
jwaltos is offline   Reply With Quote
Old 2015-11-11, 19:08   #4
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

26138 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
Nick is offline   Reply With Quote
Old 2015-11-12, 16:27   #5
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·11·41 Posts
Default

A little more info:

http://jeremykun.com/2015/11/12/a-qu...m-the-details/
danaj is offline   Reply With Quote
Old 2015-11-17, 06:55   #6
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

375410 Posts
Default

Quote:
Originally Posted by danaj View Post
Jeremy Kun adds:
Quote:
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/
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: 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!
only_human is offline   Reply With Quote
Old 2017-01-10, 12:44   #7
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

3×11×43 Posts
Default

Update from Babai:
http://people.cs.uchicago.edu/~laci/update.html
Nick is offline   Reply With Quote
Old 2019-12-14, 15:25   #8
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

141910 Posts
Default

New open journal:
https://www.advancesincombinatorics.com/
Nick is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Stacking boxes - combinatorics? Ken_g6 Puzzles 15 2010-08-04 23:30
Other news Cruelty Riesel Prime Search 41 2010-03-08 18:46
The news giveth, the news taketh away... NBtarheel_33 Hardware 17 2009-05-04 15:52
News KEP Riesel Base 3 Attack 4 2008-12-17 11:54
Combinatorics Kees Puzzles 6 2006-05-13 06:58

All times are UTC. The time now is 09:40.

Mon Aug 3 09:40:47 UTC 2020 up 17 days, 5:27, 0 users, load averages: 1.17, 1.20, 1.23

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.