Seminar Series: The Limits of Symmetric Computation

9. listopadu 2018, 9:00 (Uložit do kalendáře)

Refektář Mendelova muzea, Mendlovo náměstí 157/1

Anuj Dawar, University of Cambridge, UK

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.