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
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 
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.
Already confirming Babai’s result?
http://arxiv.org/abs/1511.02460
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.
Thanks. I intend only to Babai’s work referenced in 1.1.
Laszlo’s first abstract mentions he has also obtained a quasi-polynomial time algorithm for string isomorphism. What exactly is the string isomorphism problem?
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.
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.
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.