{\huge The World Series Of Complexity Theory}

László's three talks \vspace{.5in}

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 make it into 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 $latex {A_{n}}&fg=000000$ with $latex {n \ge 5}&fg=000000$;
2. A group of Lie type; or
3. One of the $latex {26}&fg=000000$ 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 $latex {A_{n}}&fg=000000$ with $latex {n \ge 5}&fg=000000$ 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 $latex {n}&fg=000000$, 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 first post:

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\''oré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.