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 - Laszlo Babai (Chicago)
DTSTART;TZID=Europe/London:20160412T143000
DTEND;TZID=Europe/London:20160412T160000
UID:TALK65432AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/65432
DESCRIPTION:Towards the end of 2015\, Professor Laszlo Babai o
f the University of Chicago announced a result whi
ch was immediately hailed as the best result in co
mplexity theory for several decades. He will give
two 90-minute 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 aimed at a general audience\, and are\ndistin
ct from his talk on Thursday in the "Quantum Algor
ithms" workshop.\n\nOne of the fundamental computa
tional problems in the complexity\nclass NP on Kar
p's 1973 list\, the Graph Isomorphism problem (GI)
asks to decide whether or not two given graphs ar
e isomorphic.\n\nWhile program packages exist that
solve this problem remarkably\nefficiently in pra
ctice (McKay\, Piperno\, and others)\, for\ncomple
xity 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-ca
se complexity has stood at $\\exp(O(\\sqrt{v\\log
v}))$\n(Luks\, 1983) for decades\, where $v$ is th
e number of vertices.\n\nBy addressing the bottlen
eck situation for Luks's method\, we\nhave recentl
y reduced this ``moderately exponential'' upper bo
und to quasipolynomial\, i.e.\, $\\exp((\\log v)^c
)$.\n\nWe actually solve the more general *string
isomorphism* problem (SI)\n(``can a given string b
e transformed into another given string\nunder the
action of a given permutation group ?'')\,\ndefin
ed in Luks's seminal 1980/82 paper (see below) tha
t introduced\npowerful group theoretic divide-and-
conquer methods in the design\nof SI and GI algori
thms.\n\nWe attack the bottleneck situation for Lu
ks's method through\nlocal/global interaction. Ke
y role is played by a group theoretic\nlemma that
enables the construction of global automorphisms o
ut of\nlocal information. The lemma is used to cr
eate ``local\ncertificates'' of full symmetry or i
ts 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 multipl
icative cost\,\nleading to quasipolynomial recurre
nce. This reduction is\naccomplished via combinat
orial partitioning techniques.\n\nThe first talk w
ill focus on the core group theoretic method\; in\
nthe second talk we shall discuss the combinatoria
l partitioning\ntechniques.\n\nElements of undergr
aduate-level group theory will be assumed.\n\nThe
paper is available at arXiv:1512.03547.\n\nHelpfu
l reading:\n\nE.M. Luks\, Isomorphism of graphs of
bounded valence can be tested in polynomial time\
, J. Comp. Sys. Sci.\, 25:42--65\, 1982. \n\n
LOCATION:CMS\, MR2
CONTACT:HoD Secretary\, DPMMS
END:VEVENT
END:VCALENDAR