Anuj Dawar

Professor of Logic and Algorithms, University of Cambridge

He is an expert in the applications of logic to computer science. His work is focused on areas of theoretical computer science where logical and combinatorial methods combine in the study of algorithms. In these, he has established a position of leadership and a wide network of collaborations. He has made foundational contributions in finite model theory and its connections with the logical foundations of computational complexity. Achievements in this domain include characterization of complexity classes as definability classes of finite relational structures; the use of these to analyse the expressive power of query languages for relational databases, especially on well-structured data; establishing new relationships between definability and parameterized complexity; extending the relationship between classical logics and modal logics studied in verification and knowledge representation; and fundamental contributions to the study of the complexity of games. His recent work has focused on the role of symmetry in complexity theory, linking symmetry in logic, combinatorial optimization and circuit complexity, establishing the limits of symmetric classical algorithms, and exposing where and in what way efficient algorithms must break symmetries. He was recently awarded an ERC advanced grant to extend this work.