The Limits of Symmetric Computation
- Date: Friday 15 October 2021, 14:00 – 15:00
- Location: Online
- Cost: Free
Join guest speaker Prof. Anuj Dawar from the University of Cambridge as he considers a natural restriction to symmetric algorithms.
The most famous open problem in theoretical computer science, 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. Prof. Anuj Dawar will 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.
This talk will take place online on Zoom, click here to join: Join Zoom Meeting
Meeting ID: 890 9432 6930
Organised by Karim Djemame