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)
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.
