11 April 2016

Organised in collaboration with the School of Mathematics, University of Bristol, UK

Group Theory and Algorithms: The Graph Isomorphism Problem

László Babai , Department of Computer Science and Mathematics, University of Chicago, USA

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.

Familiarity with basic concepts of group theory (such as kernel of a homomorphism) will be assumed.

---

For more information please email the Heilbronn events team at  heilbronn-coordinator@bristol.ac.uk

Information on past and future colloquia is available here

Join the Heilbronn Event mailing list to keep up to date with our upcoming event