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:The Archimedeans (CU Mathematical Society)
SUMMARY:The Limits of Symmetric Computation - Anuj Dawar (
University of Cambridge)
DTSTART;TZID=Europe/London:20191122T190000
DTEND;TZID=Europe/London:20191122T200000
UID:TALK132289AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/132289
DESCRIPTION:The most famous open problem in theoretical comput
er science\, known as the P vs. NP problem challen
ges us to prove that for some natural search probl
ems\, no efficient algorithm is possible. At the
moment\, we have no idea how to prove such a state
ment. In order to make meaningful progress\, we c
an restrict the class of algorithms we consider an
d show that\, within these restrictions\, no effic
ient algorithm exists. In this talk\, I consider
a natural restriction to symmetric algorithms. I
explain how symmetries arise naturally in computat
ional problems and why algorithms that respect the
se symmetries have inherent limitations. Many of
our most powerful algorithmic techniques are symme
try preserving\, while others are not. Exploring t
hese limits offers a rich research agenda combinin
g logic\, algebra and combinatorics with algorithm
s.
LOCATION:MR2\, Centre for Mathematical Sciences
CONTACT:Valentin HÃ¼bner
END:VEVENT
END:VCALENDAR