Laci Babai and Graph Isomorphism

Next Tuesday, a week from today, Laci Babai will talk at the University of Chicago about a new algorithm that solves graph isomorphism in quasipolynomial time. There should also be a follow-up talk the following Thursday that, by a lucky coincidence, I will be able to attend, and then report back.

Meanwhile, if you have any gossip on the proof, then, by any means, go ahead and share it in the comments.

24 thoughts on “Laci Babai and Graph Isomorphism

  1. Pingback: Shtetl-Optimized » Blog Archive » G. Phi. Fo. Fum.

  2. I don’t have any insider info, so this is purely speculation, but he did publish a very interesting paper in ITCS 2014 on structure of automorphism groups of strongly regular graphs, that did not have an immediate algorithmic application but would indeed be a very important step on the way to a quasipolynomial time algorithm for strongly regular graphs.

    Since the previously best-known GI algorithm is based on the polynomial time algorithm for bounded-degree graphs, which in turn is based on the structure of automorphism groups of bounded-degree graphs, it’s extremely plausible that his ITCS paper has been leveraged into a quasipolynomial time algorithm that works in a divide-and-conquer fashion based on this structure theorem…but even assuming that is the case, there is still the mystery of how a structure theorem about _strongly regular_ graphs is somehow applied to the general case; isomorphism testing of strongly regular graphs is/was not known to be GI-complete, and that by itself would have been a major result!

    And indeed, his ITCS paper did depend on the classification of finite simple groups.

  3. Pingback: A Big Result On Graph Isomorphism | Gödel's Lost Letter and P=NP

  4. Pingback: Cold Off The Press! | On The Shoulders Of Windmills

  5. Pingback: Theoretical CS Opportunities at Harvard | Windows On Theory

  6. Pingback: TECNOLOGÍA » A Big Result On Graph Isomorphism

  7. Is it expected that the algorithm produces an isomorphism in that time (in the case the graphs are isomorphic), or just that it answers yes/no to the isomorphism question in quasipoly time?

  8. The problem is self-reducible in such a way that an algorithm that answers the yes/no question can be converted, with polynomial slow-down, to an algorithm that outputs an isomorphism if one exists

  9. On Twitter @gabegaster was live-tweeting through the talk and described some of the essential parts. I think the impressive take-home message is that the algorithm seems actually quite a bit simpler than I would have thought, or else possibly it was just presented so brilliantly as to appear simple.

  10. Pingback: A canonical labeling technique by Brendan McKay and isomorphism testing of deterministic finite automata | Gentzen translated

  11. Pingback: Babai breakthru: graph isomorphism in quasipolynomial time | Turing Machine

  12. Pingback: A Primer on Graph Isomorphism | TRIFORCE STUDIO

  13. Pingback: G. Phi. Fo. Fum. | TRIFORCE STUDIO

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s