Title: The Limits of Symmetric Computation

Speaker: Professor Anuj Dawar, University of Cambridge, UK

Time: 10:00 am, August 16th (Thursday), 2018.

Venue: Lecture room (Room 334), Building 5, Software Park, Chinese Academy of Sciences

Abstract:

　　Lower bounds for many NP-hard problems have been proved for restricted circuit models. In this talk I introduce a restriction to symmetric circuits, which captures a natural property of algorithms that respect symmetries of their input. I show that lower bounds on such circuits can be derived from inexpressibility results in logic studied in finite model theory. Combining this with the rich expressive power of these logics, allows us to derive lower bounds for strong approximation methods based on semi-definite programming. Exploring the limits of symmetric computation offers a rich research vista bringing together logic, algebra and combinatorics with algorithms.

Biography:

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