The Limits of Symmetric Computation

9 November 2018
9:00 AM

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.

Speaker

Anuj Dawar

University of Cambridge, UK

Anuj Dawar is the Professor of Logic and Algorithms at the University of Cambridge, where he has been a member of the faculty since January 1999.
His research and teaching interests focus on theoretical computer science.
He is especially interested in understanding the limits of algorithmic methods in solving hard problems and developing a suite of logical and combinatorial methods for this study.
His recent work has focused on developing a theory of symmetric computation.
He obtained a Bachelor's degree from the Indian Institute of Technology, Delhi, a Master's degree from the University of Delaware and a Ph.D. from the University of Pennsylvania in 1993.
He worked as a post-doctoral researcher and a lecturer at Swansea University before moving to Cambridge in 1999. He has held visiting positions at Indiana University, Bloomington (USA), at INRIA and the University of Bordeaux (France) and at RWTH, Aachen (Germany). He served from 2013-17 as president of the European Association for Computer Science Logic. He is a Fellow of the Alan Turing Institute in London.

Share event