9/11/2018 Prof. Anuj Dawar's lecture: The Limits of Symmetric Computation
About the lecture
The most famous open problem in theoretical computer science, known as the P vs.
NP problem challenges us to prove that for some natural search problems, no
efficient algorithm is possible. At the moment, we 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 that, within these restrictions, no
efficient algorithm exists. In this talk, I consider a natural restriction to
symmetric algorithms. I explain how symmetries arise naturally in computational
problems and why algorithms that respect these symmetries have inherent
limitations. Many of our most powerful algorithmic techniques are
symmetry-preserving, while others are not. Exploring these limits offers a rich
research agenda combining logic, algebra and combinatorics with algorithms.
The lecture will be held at Mendel Museum, Refectory of Augustinian Abbey
(Mendlovo nám. 1a, Brno), 9th of November 2018, 9:00 AM
About the speaker
Anuj Dawar is the Professor of Logic and Algorithms at the University of
Cambridge.
He is a Fellow of the Alan Turing Institute in London.
