- Professor of Logic and Algorithms
- Fellow of Robinson College
Research
My research is in the broad area of Theoretical Computer Science. I am particularly interested in investigating computational complexity through the lens of logic. In the subject of descriptive complexity, we seek to characterize the complexity of problems by the difficulty of their definitions in a formal language. This has led in recent years to a fascinating study of the limits of symmetric algorithms. There is a robust notion of symmetric complexity that has emerged in this work, relating logic, circuits and linear optimization methods.
The research methods in this work are based on finite model theory which describes a range of techniques for studying the expressive power of formal logic on structures such as graphs, relational databases, program models, etc. Besides its connection to descriptive complexity, the subject has applications in database theory, verification and the analysis of games.
Themes
Publications and Talks
Publications:
Here is the list of my papers at DBLP.
I regularly write reviews for Mathematical Reviews.
Talks:
Slides from some recent talks I have given are here.
Some videos can be found on my YouTube playlists.
Professional Activities
I am editor-in-chief of ACM Transactions on Computational Logic and serve on the editorial boards of Proceedings of the Royal Society A, TheoretiCS and the FoLLI LNCS series. I served for nine years as reviews editor of the Bulletin of Symbolic Logic and have also in the past served on the editorial boards of Computability and JCSS.
I am on the committee for the ACM SigLog/EATCS/EACSL Alonzo Church award. I served on the award committee for the EATCS and ACM SigACT Gödel Prize (chair in 2020). I served on the award committee for the EATCS-IPEC Nerode award (chair in 2022). I chaired the committee for the S. Barry Cooper Prize in 2020 and 2023. I served as president of the European Association for Computer Science Logic for five years until the end of 2017. In this capacity, I also chaired the jury for the Ackermann Award. In 2014 and 2015, I served as chair of the jury for the ACM-India Doctoral Dissertation Award.
In 2016, I co-organised a semester on Logical Structures in Computation at the Simons Institute for the Theory of Computing at Berkeley. I served as a principal organiser of the programme on Logic and Algorithms at the Isaac Newton Institute of Mathematical Sciences from 16 January to 7 July 2006.
I am on the advisory board for the Vienna Center for Logic and Algorithms.
Teaching
During 2024-25 I am on sabbatical leave.
Courses I have lectured in the past include:
- Computation Theory for Part 1B students.
- Topics in Logic and Complexity for Part 3 and the MPhil ACS.
- Quantum Computing for Part 2 students.
- Complexity Theory for Part 1B students.
- Database Theory for Part 2 students
- Regular Languages and Finite Automata for Part 1A students
- Introduction to Functional Programming for Part 2 (general) and Diploma students
- Foundations of Functional Programming for Part 1B.
During Lent 2002, I lectured (jointly with Martin Hyland) a Part III Mathematics course on Infinite and Finite Model Theory.
Some notes for the course can be found here.
Research Students
I am supervising the following students for their PhD.
Students who have previously completed the PhD under my supervision are:
- David Richerby (2003)
- Pablo Arrighi (2004)
- Paul Hunter (2007)
- Timos Antonopoulos (2009)
- Bjarki Holm (2011)
- Yuguo He (2011)
- Arno Pauly (2012)
- Jannis Bulian (2016)
- Pengming Wang (2018)
- Gregory Wilsenach (2019)
- Danny Vagnozzi (2022)
- Adam Ó Conghaile (2023)
MPhil/ACS, etc. Projects
If you are interested in pursuing a Master's level research project with me, some ideas for projects I would be happy to supervise can be found here.
Some of these may also be adaptable as Part II projects and are indicated as such.
Brief Biography
Professor Anuj Dawar works in the broad area of theoretical computer science. He holds degrees from the Indian Institute of Technology (Delhi), and the University of Delaware, and a PhD from the University of Pennsylvania (1993). Before joining Cambridge in 1999, he worked at Swansea University. He has held visiting positions at Indiana University, INRIA, University of Bordeaux, and RWTH Aachen.
