Sunday, November 08, 2015

Looking forward to the GI result

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[2], 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. 

Here's hoping...


  1. --------
    GASARCH recommends to ask:
    (1) Who is making the claim?,
    (2) How likely is the claim to be true?
    (3) How likely is the claim to be provable
         with what is known today?
    In regard to (1) and (2), the morphism Babai/isomorphism ⇔ Mochizuki/IUTT(abc) is reasonably exact, but with regard to (3) the situation is totally different.

    It will be a considerable surprise (to many, including me) if Babai's proof-methods are not immediately grasped by his audience … whereas even the most expert mathematicians find Mochizuki's proof-methods to be confounding.

    That is why this week's Babai lectures, and next month's Mochizuki/IUTT(abc) conference, which individually are wonderfully interesting, are jointly (by their mathematical contrast) even more wonderfully interesting.

  2. I would suggest a fourth parameter for the claimed proves of really hard problems like the NP vs P question.
    4)Is there some really novel idea involved in the proof?
    If the proof reuses only old ideas that have been studied exhaustively it is hard to have produced somthing new and novel.