Skip to content

A Big Result On Graph Isomorphism

November 4, 2015
tags: , , , , ,
by


Jumping GI down from the nearly-exponential neighborhood to the nearly-polynomial one

laci

László Babai is one of the world experts on complexity theory, especially related to groups and graphs. He also recently won the 2015 ACM Knuth Prize, for which we congratulate him.

Today we wish to discuss a new result that he has announced that will place graph isomorphism almost in polynomial time.

More exactly László shows that Graph Isomorphism is in Quasipolynomial Time: that is time of the form

\displaystyle 2^{O(\log(n))^{c}},

for some constant {c}. Polynomial time is the case when {c=1}, but any {c} is a huge improvement over the previous best result.

Luca Trevisan already has made a post on this result, and Scott Aaronson likewise. Luca further promises to be in Chicago next Tuesday when László gives his talk on the result—here is the abstract of the talk:

We outline an algorithm that solves the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (SI) and Coset Intersection (CI) in quasipolynomial {(\exp(\mathsf{polylog} \ n))} time.

The best previous bound for GI was {\exp(\sqrt{n \log n})}, where {n} is the number of vertices ([Eugene] Luks, 1983). For SI and CI the best previous bound was similar, {\exp(\sqrt{n}(\log n)^c)}, where {n} is the size of the permutation domain (the speaker, 1983).

He is following this up with a talk on Thursday the 12th at 4:30 in the Mathematics Department’s Group Theory seminar titled, “A little group theory goes a long way: the group theory behind recent progress on the Graph Isomorphism Problem.”

Why Best Result In Years

Well for starters it is a vast improvement over the complexity of GI. And while we know nothing yet about the algorithm we can make some guesses about the result. These are just guesses, but may contribute to appreciating why the result is so important.

{\bullet } The algorithm likely uses some interesting structural results about graphs and or groups. The latter connection is clear, but the former could be that the automorphism group of a graph plays an important role in GI. If these structure theorems indeed are there, they could easily help solve other problems that we have in complexity theory. David Rosenbaum, an expert on group isomorphism, raised this point to me: perhaps László’s methods will finally move group isomorphism from quasi-polynomial into polynomial time.

{\bullet} László in a 2013 paper with John Wilmes proved a quasi-polynomial time algorithm for isomorphism of structures called Steiner 2-designs that are more specialized. Not only that, they compute unique canonical forms and enumerate all the isomorphisms. A difference that makes the last thing possible, however, is that there can be at most quasi-poly many isomorphisms between Steiner 2-designs.

{\bullet } In Luca’s comment section it is raised whether or not László’s new method uses the simple group classification. The famous classification result has had a myriad of applications in theory. Many are interested in removing the reliance on this extremely deep theorem: this is in spirit like our interest in de-randomizing algorithms.

{\bullet} The word “outline” in László’s talk abstract suggests that the proof is long, not surprising, and perhaps complicated, again not surprising. László is terrific so if he says he has the result, I will bet that all is okay. Two comments I just got are “wow” and “Now it is down to factoring and short lattice vectors. Whew.”

Well, there are other intermediate problems besides these two and discrete log. Notably there is minimum circuit size, whose “umbrella” relation to GI and factoring and discrete log we covered earlier this year.

{\bullet } Raising questions about other problems. This a surprising result. Is a similar result for factoring around the corner? Or shortest vectors? GI is also one of those problems that was in sub-exponential time and was not known to be in quasi-polynomial time. Placing factoring in this complexity class would be a huge difficulty for cryptography.

Open Problems

Is the result correct? What is the structure of the theorem? Does it give counting or canonical forms? And are there any new results that may be used elsewhere in theory?

Good luck to László; we all hope that the result is correct. What a major achievement.

from → All Posts, News, Results
25 Comments leave one →
  1. Chris Peikert permalink
    November 4, 2015 3:12 pm

    Regarding crypto relevance: GI is certainly in the same category as factoring, discrete log, and lattice problems in the sense that they are “NP-intermediate.” However, the latter problems are often used as foundations for cryptography, whereas GI is not. In particular, we lack ways of generating conjectured-hard random instances of GI, whereas we do have good methods for the other problems. GI is more relevant to crypto in that it’s used as a simple example of a problem outside P that has a (perfect) zero-knowledge proof system (and so does its complement).

    Reply
  2. domotorp permalink
    November 4, 2015 4:49 pm

    Typo: factoring is around the corner twice.

    Reply
    • KWRegan permalink*
      November 4, 2015 7:29 pm

      Ah thanks—that was an artifact of merging an update from Dick while I was on the “down train” from Oxford back to London. Chris, thanks also; I was also mulling mentioning that the result seems not to impact the relations between intermediate problems shown in the referenced March post. That the train had wifi evens up the score for British transport when I had not quite completed the intended-Saturday post by the British Airways boarding time.

      Reply
  3. Magnus Wahlström permalink
    November 5, 2015 8:06 am

    Is hypergraph duality testing still intermediate?

    (For those who don’t know: You have a ground set V, and you have two set systems S and T over V. You want to know whether T is equal to the collection of all minimal hitting sets of S. This is in quasi-polynomial time, I guess essentially because any positive instance must be very large compared to |V|. But I don’t recall hearing any possible evidence for or against the existence of a polynomial-time algorithm for it.)

    Reply
    • kante permalink
      November 6, 2015 4:19 am

      the best known is still quasi-polynomial (at least no better is published). Recently (at LICS’14) Gottlob proved that it is in $DSPACE[log^2]$ (

      Reply
  4. sniffnoy permalink
    November 5, 2015 11:34 pm

    Here’s something interesting: Going by the abstract for the subsequent talk at the group theory seminar (H/T Zev Chonoles), the proof seems to rely on Schreier’s hypothesis. But so far the only proofs of Schreier’s hypothesis require the classification of finite simple groups! So implicitly the proof relies on the classification of finite simple groups (at least currently).

    Reply
  5. divisibility permalink
    November 6, 2015 3:20 pm

    Reblogged this on divisibility.wordpress.com and commented:
    I thought GI was supposed to be harder than factoring! yikes

    Reply
    • diegode permalink
      November 6, 2015 6:21 pm

      Well, since it’s an open problem if GI is in coNP, while integer factorization and shortest vector are in coNP (for IF is trivial and for SV: http://www.cims.nyu.edu/~regev/papers/cvpconp.pdf), our intuition would say that GI should be “harder” than IF and SV, but now Babai showed that our intuition is wrong!

      Reply
  6. a permalink
    November 7, 2015 7:27 pm

    How much is representation theory of Sn useful in GI?

    Reply
  7. Michael McKinnon permalink
    November 9, 2015 12:46 am

    Reblogged this on Michael McKinnon's Blog and commented:
    It’s not often that I see excitement from multiple friends in the world of academia. Everyone who appreciates these problems for what they are, and what solving them might bring to the world will be watching on with interest this week – including me!

    Reply
  8. John permalink
    November 9, 2015 1:54 pm

    http://people.cs.uchicago.edu/~laci/quasipoly.html

    Reply
  9. John Sidles permalink
    November 9, 2015 2:48 pm

    Pip states four questions and a hope:  “Is the result correct? What is the structure of the [graph isomorphism] theorem? Does it give counting or canonical forms? And are there any new results that may be used elsewhere in theory? Good luck to László; we all hope that the result is correct. What a major achievement.

    These same four questions, and the same hope, are invariant under the maps [László Babai] ⇒&nbsp[Shinichi Mochizuki] and [graph isomorphism] ⇒&nbsp[abc conjecture].

    By extension, readers of Dick and Ken’s Gödel’s Lost Letter who are interested in Babai’s work may enjoy Michael Harris’ weblog Mathematics Without Apologies (MWA), in particular Harris’ recent essay “Ideas are the currency of mathematics“ (November 7, 2015), which references an earlier MWA essay “abc and foundations“ (October 9, 2015).

    Pretty much everyone hopes that both Babai’s and Mochizuki’s ideas will stand up to critical scrutiny in the coming months. But there is a difference between them (to which Harris’ essay alludes), namely that if Babai’s mathematical ideas are viewed as (at least) moderately enlightening, then Mochizuki’s ideas must be viewed as radically enlightening.

    It will be very interesting, in coming months, to watch the STEM community grapple with these moderate-versus-radical visions of mathematical enlightenment!

    Reply
  10. Gil Kalai permalink
    December 14, 2015 2:05 pm

    Laci’s paper is on the arxive!! http://arxiv.org/abs/1512.03547

    Reply
  11. trisetyarso permalink
    March 17, 2016 3:52 am

    Reblogged this on Revolusi Sains Indonesia and commented:
    Interesting!

    Reply
  12. Yasu permalink
    April 18, 2024 8:21 am

    The graph isomorphism problem can be solved in polynomial time by obtaining the automorphisms of each graph using the spectral method and comparing the vertex lists of input two graphs.
    https://www.researchgate.net/publication/379892337_Solving_graph_isomorphism_problem_in_polynomial_time

    Reply

Trackbacks

  1. Cold Off The Press! | On The Shoulders Of Windmills
  2. A Big Result On Graph Isomorphism « Pink Iguana
  3. Theoretical CS Opportunities at Harvard | Windows On Theory
  4. Graph isomorphism | Peter Cameron's Blog
  5. Babai breakthru: graph isomorphism in quasipolynomial time | Turing Machine
  6. Un algorithme quasipolynomial pour l’isomorphisme de graphes | Thibaut Cuvelier
  7. Looking forward to the GI result | TRIFORCE STUDIO
  8. Computation and Journalism Part 2 | TRIFORCE STUDIO
  9. Polymath10-post 4: Back to the drawing board? | Combinatorics and more
  10. Babai’s Result: Still a Breakthrough | Gödel's Lost Letter and P=NP

Leave a Reply

Discover more from Gödel's Lost Letter and P=NP

Subscribe now to keep reading and get access to the full archive.

Continue reading