BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The Limits of Symmetric Computation - Anuj Dawar (University of Ca
 mbridge)
DTSTART:20191122T190000Z
DTEND:20191122T200000Z
UID:TALK132289@talks.cam.ac.uk
CONTACT:Valentin Hübner
DESCRIPTION:The most famous open problem in theoretical computer science\,
  known as the P vs. NP problem challenges us to prove that for some natura
 l search problems\, no efficient algorithm is possible.  At the moment\, w
 e have no idea how to prove such a statement.  In order to make meaningful
  progress\, we can restrict the class of algorithms we consider and show t
 hat\, within these restrictions\, no efficient algorithm exists.  In this 
 talk\, I consider a natural restriction to symmetric algorithms.  I explai
 n how symmetries arise naturally in computational problems and why algorit
 hms that respect these symmetries have inherent limitations.  Many of our 
 most powerful algorithmic techniques are symmetry preserving\, while other
 s are not. Exploring these limits offers a rich research agenda combining 
 logic\, algebra and combinatorics with algorithms.
LOCATION:MR2\, Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR