Graph isomorphism in quasi-polynomial (classical) time

Add to your list(s) Download to your calendar using vCal

• Laszlo Babai (Chicago)
• Thursday 14 April 2016, 15:30-17:30
• MR2, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

If you have a question about this talk, please contact Steve Brierley.

This talk has been canceled/deleted

One of the fundamental computational problems in the complexity class NP on Karp’s 1973 list, the Graph Isomorphism problem asks to decide whether or not two given graphs are isomorphic. While program packages exist that solve this problem remarkably efficiently in practice (McKay, Piperno, and others), for complexity theorists the problem has been notorious for its unresolved asymptotic worst-case complexity: strong theoretical evidence suggests that the problem should not be NP-complete, yet the worst-case complexity has stood at exp(O(sqrt(v log v)) (Luks, 1983) for decades, where v is the number of vertices.

By addressing the bottleneck situation for Luks’s algorithm, we recently reduced this ``moderately exponential’’ upper bound to quasipolynomial, i.e., exp((log v)^c).

The problem actually solved is more general: within the stated time bound, we solve the String Isomorphism problem, introduced by Luks in his seminal 1980 paper (see below). The input to this problem is a permutation group G acting on a set Omega of n elements, and a pair of strings, x and y, over Omega (functions that map Omega into a finite alphabet). The question is, does there exist a permutation in G that transforms x into y (``anagrams under group action’‘). (G is given by a list of generators.)

The divide-and-conquer algorithm attempts to significantly reduce n, the size of the permutation domain, at a modest multiplicative cost. This is achieved through the group theoretic ``Local Certificates’’ routine and two combinatorial partitioning routines, referred to as the ``Design Lemma’’ and the ``Split-or-Johnson’’ routine.

A group theoretic lemma is at the heart of this approach. In the talk we shall state this lemma and outline the path through which it leads to the Local Certificates. Time permitting, we shall state the combinatorial partitioning results and comment on how they are used to process the Local Certificates.

The paper is available at arXiv:1512.03547.

Helpful reading: E.M. Luks : Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comp. Sys. Sci., 25:42—65, 1982.

The talk will be followed by a drinks reception in the CMS core, to which all are invited. It is part of the Heilbronn Quantum algorithms meeting

This talk is part of the CQIF Seminar series.

This talk is included in these lists:

This talk is not included in any other list

Note that ex-directory lists are not shown.