BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Special DPMMS Colloquium
SUMMARY:Graph Isomorphism in Quasipolynomial Time I. -- Lo
cal Certificates - László Babai (Chicago)
DTSTART;TZID=Europe/London:20160412T143000
DTEND;TZID=Europe/London:20160412T160000
UID:TALK65433AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/65433
DESCRIPTION:Two 90-minute talks will be given\, about testing
graph isomorphism in\nquasipolynomial time. These
talks are aimed at a general audience\, and are\nd
istinct from the talk on Thursday in the "Quantum
Algorithms" workshop.\n\n\nOne of the fundamental
computational problems in the complexity\nclass NP
on Karp's 1973 list\, the Graph Isomorphism probl
em (GI) asks to decide whether or not two given gr
aphs are isomorphic.\n\nWhile program packages exi
st that solve this problem remarkably\nefficiently
in practice (McKay\, Piperno\, and others)\, for\
ncomplexity theorists the problem has been notorio
us for its\nunresolved asymptotic worst-case compl
exity: strong theoretical\nevidence suggests that
the problem should not be NP-complete\, yet\nthe w
orst-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'' u
pper bound to quasipolynomial\, i.e.\, $\\exp((\\l
og v)^c)$.\n\nWe actually solve the more general *
string isomorphism* problem (SI)\n(``can a given s
tring be transformed into another given string\nun
der the action of a given permutation group ?'')\,
\ndefined in Luks's seminal 1980/82 paper (see bel
ow) that introduced\npowerful group theoretic divi
de-and-conquer methods in the design\nof SI and GI
algorithms.\n\nWe attack the bottleneck situation
for Luks's method through\nlocal/global interacti
on. Key role is played by a group theoretic\nlemm
a that enables the construction of global automorp
hisms out of\nlocal information. The lemma is use
d to create ``local\ncertificates'' of full symmet
ry or its absence. Subsequently the\nlocal certif
icates are aggregated to a canonically embedded st
ructure which is then exploited to produce a signi
ficant\nreduction of the problem size at moderate
multiplicative cost\,\nleading to quasipolynomial
recurrence. This reduction is\naccomplished via c
ombinatorial partitioning techniques.\n\nThe first
talk will focus on the core group theoretic metho
d\; in\nthe second talk we shall discuss the combi
natorial partitioning\ntechniques.\n\nElements of
undergraduate-level group theory will be assumed.\
n\nThe paper is available at arXiv:1512.03547.\n\
nHelpful reading:\n\nE.M. Luks\, Isomorphism of gr
aphs of bounded valence can be tested in polynomia
l time\, J. Comp. Sys. Sci.\, 25:42--65\, 1982.
\n\n
LOCATION:CMS\, MR2
CONTACT:HoD Secretary\, DPMMS
END:VEVENT
END:VCALENDAR