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
   - László Babai  (Chicago)
DTSTART:20160412T133000Z
DTEND:20160412T150000Z
UID:TALK65433@talks.cam.ac.uk
CONTACT:HoD Secretary\, DPMMS
DESCRIPTION:Two 90-minute talks will be given\, about testing graph isomor
 phism in\nquasipolynomial time. These talks are aimed at a general audienc
 e\, and are\ndistinct from the talk on Thursday in the "Quantum Algorithms
 " workshop.\n\n\nOne of the fundamental computational problems in the comp
 lexity\nclass NP on Karp's 1973 list\, the Graph Isomorphism problem (GI) 
 asks to decide whether or not two given graphs are isomorphic.\n\nWhile pr
 ogram packages exist that solve this problem remarkably\nefficiently in pr
 actice (McKay\, Piperno\, and others)\, for\ncomplexity theorists the prob
 lem has been notorious for its\nunresolved asymptotic worst-case complexit
 y: strong theoretical\nevidence suggests that the problem 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 vertice
 s.\n\nBy addressing the bottleneck situation for Luks's method\, we\nhave 
 recently reduced this ``moderately exponential'' upper bound to quasipolyn
 omial\, i.e.\, $\\exp((\\log v)^c)$.\n\nWe actually solve the more general
  *string isomorphism* problem (SI)\n(``can a given string be transformed i
 nto another given string\nunder the action of a given permutation group ?'
 ')\,\ndefined in Luks's seminal 1980/82 paper (see below) that introduced\
 npowerful group theoretic divide-and-conquer methods in the design\nof SI 
 and GI algorithms.\n\nWe attack the bottleneck situation for Luks's method
  through\nlocal/global interaction.  Key role is played by a group theoret
 ic\nlemma that enables the construction of global automorphisms out of\nlo
 cal information.  The lemma is used to create ``local\ncertificates'' of f
 ull symmetry or its absence.  Subsequently the\nlocal certificates are agg
 regated to a canonically embedded structure which is then exploited to pro
 duce a significant\nreduction of the problem size at moderate multiplicati
 ve cost\,\nleading to quasipolynomial recurrence.  This reduction is\nacco
 mplished via combinatorial partitioning techniques.\n\nThe first talk will
  focus on the core group theoretic method\; in\nthe second talk we shall d
 iscuss the combinatorial partitioning\ntechniques.\n\nElements of undergra
 duate-level group theory will be assumed.\n\nThe paper is available at  ar
 Xiv:1512.03547.\n\nHelpful reading:\n\nE.M. Luks\, Isomorphism of graphs o
 f 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