COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > The Archimedeans (CU Mathematical Society) > The Limits of Symmetric Computation

## The Limits of Symmetric ComputationAdd to your list(s) Download to your calendar using vCal - Anuj Dawar (University of Cambridge)
- Friday 22 November 2019, 19:00-20:00
- MR2, Centre for Mathematical Sciences.
If you have a question about this talk, please contact Valentin Hübner. 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. This talk is part of the The Archimedeans (CU Mathematical Society) series. ## This talk is included in these lists:- Guy Emerson's list
- MR2, Centre for Mathematical Sciences
- The Archimedeans (CU Mathematical Society)
- bld31
- ob366-ai4er
Note that ex-directory lists are not shown. |
## Other listsHeritage in the making: dealing with legacies of Fascist Italy and Nazi Germany Kazakhstan’s Bid to Secure a Non-permanent Seat on the UN Security Council for 2017-18 Science talks## Other talksHow do Housing Markets Respond to the Threat of Sea Level Rise? Journalism and News Media (6-7 February 2020) Content and Language Integrated Learning (CLIL) in Multilingual Classrooms: From Conceptualisation to Implementation to Professional Development Understanding Anger - An interactive talk Plant Sciences Departmental Seminar Centrosome amplification and cancer: reaching out |