As you all know Laszlo Babai will give a talk Tuesday Nov 10 on a result: GI in quasipolynomial time (2 to a polylog). Other theory blogs have already commented on this (GLL,In Theory,Shetl-Opt)
When I was in Graduate School (early 1980's) it looked like GI would get into P. Three key results: graphs of bounded degree, graphs of bounded genus, graphs of bounded eigenvalue multiplicity, were all shown to be in P. These results used group theory and linear algebra in serious ways so the thought was that more advanced group theory, perhaps the classification of all finite simple groups (CFSG) would be used to show GI in P. If CFSG was used in an algorithm for GI in P then the algorithm might have an enormous constant, but that's okay since the quest for GI in P is not for practical reasons (I think that all the people who want to solve it already have fast enough algorithms) . I was looking forward to the debates on if an algorithm with that big a constant would count as poly time (I would say yes). But no algorithm for GI in P, using CFSG or not, was found. Also note that it was possible (and is still possible) that GI is NOT in P. In my 2012 survey of P vs NP I also asked about GI. Of the 20 people who responded 14 thought GI is in P, 6 thought not. Note that GI is not known to be in co-NP or BPP. It IS in IP, and if GI was NPC
then PH collapses, so it is unlikely that GI is NP-complete. This tells us NOTHING about whether it is in P.
An analogous thing happened with PRIMES. Lots of results that got it almost in P, lots of hard number theory used, but then the progress stopped. Two differences: Most people thought PRIMES IS in P (likely because it's in coNP and BPP),and this was finally proven in 2002.
Is Babai's proof likely to be correct? There are three parameters to consider when looking at that question: (1) Who is making the claim?, (2) How likely the claim is to be true?, (3) How likely the claim is to be provable with what is known today?.You can give different weights to each one in different combinations..
Laszlo Babai is an expert in GI with a track record in the area. (reading that over again it undersells the case- Babai is, as the kids say, awesome!) That GI is in quasipolynomial time is quite believable. Even those 6 who think that Gi is not in P might believe that. Its harder to know if today's techniques are up to the task; however, there are no results like `group theory won't suffice' or any kind of obstacles, so certainly the claim seems provable with todays technology.