1. 14

This was announced last month; the news item is because the paper is now in preprint. The abstract (which suffers a bit from the lack of LaTeX, sorry):

We show that the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (under group action) (SI) and Coset Intersection (CI) can be solved in quasipolynomial ($\exp((\log n)^{O(1)})$) time. The best previous bound for GI was $\exp(O(\sqrt{n\log n}))$, where $n$ is the number of vertices (Luks, 1983); for the other two problems, the bound was similar, $\exp(\tilde{O}(\sqrt{n}))$, where $n$ is the size of the permutation domain (Babai, 1983).

The algorithm builds on Luks’s SI framework and attacks the barrier configurations for Luks’s algorithm by group theoretic “local certificates” and combinatorial canonical partitioning techniques. We show that in a well-defined sense, Johnson graphs are the only obstructions to effective canonical partitioning.


  2. 2

    If this can be turned into a good set of library routine…. I can see this making quite a practical impact.

    I keep bumping into problems at the “everyday” level of analyzing code / optimizing code / … which relate closely to this problem.

    1. 4

      Not likely. From a relatively accessible post discussing the details:

      Nevertheless, the common understanding is that pretty much anybody who needs to solve GI on a practical level can do so efficiently. The heuristics work well.

      That’s actually my biggest problem with the Quanta article: it doesn’t make clear that, although this is a big theoretical breakthrough, it is unlikely to have any short-term practical impact.

      1. 2

        Heuristics are also getting better. For practical algorithms for graph isomorphism, this paper summarizes advances since NAUTY(1980) well. http://arxiv.org/abs/1301.1493

    2. 1

      Oh, nifty find Irene!

      Thanks for linking the paper. :)

      1. 1

        Would it be worthwhile to get some LaTeX library setup? I hear KaTeX (Kahn Academy’s JavaScript LaTeX parser/renderer) is quite good, both in performance and the rendering itself. I don’t know how useful such an addition would be, but it may be worth discussing.

        1. 1

          Maybe. The math tag gets a decent amount of use, but nothing else on the first page of hits for it attempted to use math notation in the description or comments. :) I’m not sure whether that reflects a lack of need or a lack of ability.