BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Graph isomorphism in quasi-polynomial (classical) time - Laszlo Ba
 bai (Chicago)
DTSTART:20160414T143000Z
DTEND:20160414T163000Z
UID:TALK65010@talks.cam.ac.uk
CONTACT:Steve Brierley
DESCRIPTION:One of the fundamental computational problems in the complexit
 y class NP on Karp's 1973 list\, the Graph Isomorphism problem asks to dec
 ide whether or not two given graphs are isomorphic.  While program package
 s exist that solve this problem remarkably efficiently in practice (McKay\
 , Piperno\, and others)\, for complexity theorists the problem has been no
 torious for its unresolved asymptotic worst-case complexity: strong theore
 tical evidence suggests that the problem should not be NP-complete\, yet t
 he worst-case complexity has stood at exp(O(sqrt(v log v)) (Luks\, 1983) f
 or decades\, where v is the number of vertices.\n\nBy addressing the bottl
 eneck situation for Luks's algorithm\, we recently reduced this ``moderate
 ly exponential'' upper bound to quasipolynomial\, i.e.\, exp((log v)^c).\n
 \nThe problem actually solved is more general: within the stated time boun
 d\, we solve the String Isomorphism problem\, introduced by Luks in his se
 minal 1980 paper (see below). The input to this problem is a permutation g
 roup 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 qu
 estion 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.)\n
 \nThe divide-and-conquer algorithm attempts to significantly reduce n\, th
 e size of the permutation domain\, at a modest multiplicative cost.   This
  is achieved through the group theoretic ``Local Certificates'' routine an
 d two combinatorial partitioning routines\, referred to as the ``Design Le
 mma'' and the ``Split-or-Johnson'' routine.\n\nA 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 p
 ermitting\, we shall state the combinatorial partitioning results and comm
 ent on how they are used to process the Local Certificates.\n\nThe paper i
 s available at  arXiv:1512.03547.\n\nHelpful reading: E.M. Luks : Isomorph
 ism of graphs of bounded valence can be tested in polynomial time.   J. Co
 mp. Sys. Sci.\, 25:42--65\, 1982.\n\n\nThe talk will be followed by a drin
 ks reception in the CMS core\, to which all are invited. It is part of the
  "Heilbronn Quantum algorithms meeting":http://www.qi.damtp.cam.ac.uk/node
 /267\n
LOCATION:MR2\, Centre for Mathematical Sciences\, Wilberforce Road\, Cambr
 idge
END:VEVENT
END:VCALENDAR