Skip to content

The World Series Of Complexity Theory

November 9, 2015


László’s three talks

BabaiChalkTalk
Chicago Chronicle source

László Babai must be busy getting ready for his series of talks.

Today Ken and I wish to discuss one issue that has come up in comments about his result.

By the way, the big event this Tuesday is not the Republican Debate on Fox, but Laci’s talk. It’s too bad for Chicago that the Cubs didn’t reach this year’s World Series, but these talks will make up for it.

Use Of Simple Group Classification

Recall that the simple group classification theorem says:

Theorem 1 Every nonabelian simple finite group is either:

  1. An alternating group {A_{n}} with {n \ge 5};

  2. A group of Lie type; or

  3. One of the 26 sporadic groups.

How about the following weaker version of the simple group classification theorem:

Theorem 2 Every large enough nonabelian simple finite group is either {A_{n}} with {n \ge 5} or a Lie type group.

I am not saying that this could be easier to prove. No. But it may be sufficient for many of the applications in computer science. One example is that testing isomorphism of finite simple groups in polynomial time needs only the fact of their being 2-generated, for large enough {n}, and so doesn’t care exactly how many sporadic groups there are. This seems like a nice point that we should be aware of, especially if it is relevant for the new GI result.

A Little More Info

A third talk has been announced on Laci’s page two weeks from Tuesday, titled “Graph Isomorphism in Quasipolynomial Time II: the ‘Split-or-Johnson’ routine.” Its abstract starts off with:

In this second talk of the series we present the details of the canonical partitioning algorithms required for the master algorithm.

The abstract for tomorrow’s talk also has a third paragraph which we didn’t notice before our post last Wednesday:

In this first talk we give an overview of the algorithm and present the core group-theoretic divide-and-conquer routine, the “Local Certificates algorithm.” Familiarity with undergraduate-level group theory will be assumed.

The second abstract mentions Otto Schreier’s conjecture that the outer-automorphism group of any finite simple group is solvable, which was proved by the classification. So it is possible that the divide-and-conquer routine exploiting this solvability may encounter the sporadic groups in its recursion after all. Or it might bypass them. We just don’t know, but we look forward to knowing.

Open Problems

Good luck to Laci—break a leg. Apparently this is also a good-luck expression in Hungarian but they go a bit further: kéz- és lábtörést, meaning literally, “hand and foot fractures.” Well if this is being given as a chalk talk the former may come into play.

We also note that today’s Google doodle features Hedy Lamarr and her frequency-hopping invention.

Update Tue. 11/10 8pm: Gabriel Gaster has tweeted a running commentary on the talk: https://twitter.com/gabegaster. And reading it made me(us) realize “d’oh”—of course the algorithm could bypass the sporadic groups since for large enough n it can just switch over to brute force at that point in the recursion. This seems true here—so Dick’s point about simpler classification is enough—and we just talked about how generally this might apply for any algorithm based (for the time being) on the classification. Moreover, it seems the use of the Schreier consequence for outer-automorphism groups doesn’t care about the simple groups involved, just that the “outer” groups are solvable. The proof does also use Luks’s algorithm as part of a three-way fencing off of cases (i.e., if you encounter an obstacle to Luks’s algorithm then something else good happens), which speculation I chose not to add on Wednesday.

9 Comments leave one →
  1. November 10, 2015 2:52 am

    Already confirming Babai’s result?

    http://arxiv.org/abs/1511.02460

    • November 10, 2015 7:50 am

      Ibrahim: that’s bounded genus g, and it’s about showing fixed-parameter tractability with respect to g. Before the runtime was n^{O(g)}. That paper is f(g) * n.

      • November 11, 2015 2:49 am

        Thanks. I intend only to Babai’s work referenced in 1.1.

  2. November 10, 2015 10:53 pm

    Laszlo’s first abstract mentions he has also obtained a quasi-polynomial time algorithm for string isomorphism. What exactly is the string isomorphism problem?

    • November 11, 2015 12:42 am

      To my mind it’s whether two jumbled up total orders are related by a character-respecting map. Strings x and y over alphabet {a,…,h}, say, are defined by tuples of relations (X_a(i),…,X_h(i),LX(i,j)) where i ranges over the domain {0,…,n-1}, likewise j. If y = (Y_a(i),…,Y_h(i),LY(i,j)) then the question is whether there is a permutation g such that for all i and j:

      X_a(i) ↔ Y_a(g(i)), …, X_h(i) ↔ Y_h(i), and LX(i,j) ↔ LY(g(i),g(j)).

      The reduction from GI may be allowed to make alphabet size of the target instance depend on the size of the graph. Otherwise, I don’t see it.

    • November 11, 2015 3:35 am

      Maybe Joshua Grochow’s answer showing how to reduce graph isomorphism to string isomorphism (over a binary alphabet) gives a good indication about the relevant string isomorphism problem here. Note that we are given a subgroup of the symmetric group here, and we are only looking for isomorphisms from that subgroup.

  3. Laci Pyber permalink
    September 25, 2016 9:59 am

    I have a note on the arxiv which gives a “A CFSG-free analysis of Babai’s quasipolynomial GI algorithm” (unpublished yet but checked by many people). BTW “Theorem 2” is called CLFSG (L=Large) . Some clever people did write/think about the possibility of proving this. An amazing result of Larsen and Pink may be viewed as a bounded dimensional version of this.

Trackbacks

  1. Babai breakthru: graph isomorphism in quasipolynomial time | Turing Machine
  2. Blasts From the Past | Gödel's Lost Letter and P=NP

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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