The World Series Of Complexity Theory
László’s three talks
|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:
- An alternating group with ;
- A group of Lie type; or
- 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 with 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 , 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.
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.
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.