László Babai (U. Chicago) "Finite permutation groups and the Graph Isomorphism problem"

Mon, 07/11/201610:40-12:50
Israel Institute for Advanced Studies, Safra campus, Givat Ram
* This talk is joint with the 20th Midrasha Mathematicae: 60 faces to groups, celebrating Alex Lubotzky's 60th birthday.
The full program for AlexFest, Nov. 6--11, is detailed here:
Speaker: László Babai (University of Chicago)
Title: Finite permutation groups and the Graph Isomorphism problem
Updated abstract:
The Graph Isomorphism (GI) problem is the algorithmic problem
to decide whether or not two given finite graphs are isomorphic. Recent
work by the speaker has brought the worst-case complexity of this problem
down from moderately exponential, exp(sqrt(
n log n)) (Luks, 1983) to quasipolynomial
(exp((log n)^c)), where n is the number of vertices. We build on Luks’s
group theoretic divide-and-conquer technique (1980) and address the method’s
We shall also comment on the related “Group Isomorphism problem,” a
major barrier to further progress on GI. We shall explain a recent construction
of certain class-2 nilpotent groups by Glauberman and Grabowski (2015)
pertaining to an approach suggested by Gowers to this problem.