BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Graph Isomorphism in Quasipolynomial Time I. -- Local Certificates
   -  Laszlo Babai  (Chicago)
DTSTART:20160412T133000Z
DTEND:20160412T150000Z
UID:TALK65432@talks.cam.ac.uk
CONTACT:HoD Secretary\, DPMMS
DESCRIPTION:Towards the end of 2015\, Professor Laszlo Babai of the Univer
 sity of Chicago announced a result which was immediately hailed as the bes
 t result in complexity theory for several decades. He will give two 90-min
 ute talks on this result of his in CMS\, (12th and 13th April) in which he
  hopes to give a fairly detailed outline of his proof. These talks are aim
 ed at a general audience\, and are\ndistinct from his talk on Thursday in 
 the "Quantum Algorithms" workshop.\n\nOne of the fundamental computational
  problems in the complexity\nclass NP on Karp's 1973 list\, the Graph Isom
 orphism problem (GI) asks to decide whether or not two given graphs are is
 omorphic.\n\nWhile program packages exist that solve this problem remarkab
 ly\nefficiently in practice (McKay\, Piperno\, and others)\, for\ncomplexi
 ty theorists the problem has been notorious for its\nunresolved asymptotic
  worst-case complexity: strong theoretical\nevidence suggests that the pro
 blem should not be NP-complete\, yet\nthe worst-case complexity has stood 
 at $\\exp(O(\\sqrt{v\\log v}))$\n(Luks\, 1983) for decades\, where $v$ is 
 the number of vertices.\n\nBy addressing the bottleneck situation for Luks
 's method\, we\nhave recently reduced this ``moderately exponential'' uppe
 r bound to quasipolynomial\, i.e.\, $\\exp((\\log v)^c)$.\n\nWe actually s
 olve the more general *string isomorphism* problem (SI)\n(``can a given st
 ring be transformed into another given string\nunder the action of a given
  permutation group ?'')\,\ndefined in Luks's seminal 1980/82 paper (see be
 low) that introduced\npowerful group theoretic divide-and-conquer methods 
 in the design\nof SI and GI algorithms.\n\nWe attack the bottleneck situat
 ion for Luks's method through\nlocal/global interaction.  Key role is play
 ed by a group theoretic\nlemma that enables the construction of global aut
 omorphisms out of\nlocal information.  The lemma is used to create ``local
 \ncertificates'' of full symmetry or its absence.  Subsequently the\nlocal
  certificates are aggregated to a canonically embedded structure which is 
 then exploited to produce a significant\nreduction of the problem size at 
 moderate multiplicative cost\,\nleading to quasipolynomial recurrence.  Th
 is reduction is\naccomplished via combinatorial partitioning techniques.\n
 \nThe first talk will focus on the core group theoretic method\; in\nthe s
 econd talk we shall discuss the combinatorial partitioning\ntechniques.\n\
 nElements of undergraduate-level group theory will be assumed.\n\nThe pape
 r is available at  arXiv:1512.03547.\n\nHelpful reading:\n\nE.M. Luks\, Is
 omorphism of graphs of bounded valence can be tested in polynomial time\, 
   J. Comp. Sys. Sci.\, 25:42--65\, 1982. \n\n
LOCATION:CMS\, MR2
END:VEVENT
END:VCALENDAR