Title: Graph isomorphisms in quasi-polynomial time,
Abstract: Let us be given two graphs $\Gamma_1$, $\Gamma_2$ of $n$ vertices. Are they
isomorphic? If they are, the set of isomorphisms from $\Gamma_1$ to $\Gamma_2$
can be identified with a coset $H\cdot\pi$ inside the symmetric group on $n$
elements. How do we find $\pi$ and a set of generators of $H$?
The challenge of giving an always efficient algorithm answering these
questions remained open for a long time. Babai has recently shown how to solve
these problems -- and others linked to them -- in quasi-polynomial time, i.e.
in time $\exp\left(O(\log n)^{O(1)}\right)$. His strategy is based in part on
the algorithm by Luks (1980/82), who solved the case of graphs of bounded
degree.