ANUJ DAWAR
Professor of Logic and Algorithms
in the Department of Computer
Science and Technology, University of Cambridge.
Fellow of Robinson
College.
Fellow of the Alan Turing Institute.
Contact Info:
anuj.dawarcl.cam.ac.uk
Department of Computer Science and Technology
University of Cambridge J.J. Thomson Avenue Cambridge CB3 0FD, England. |
Phone: +44 1223 334408
Fax: +44 1223 334678 |
Office: FE20 |
External Professional Roles:
I chaired the 2020 award committee for
the EATCS and ACM
SigACT Gödel Prize.
I am on the award committee for the EATCS-IPEC Nerode award. I chair the committee for the S. Barry Cooper prize.
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
During 2016, I co-organised a semester on Logical Structures in Computation at the Simons Institute for the Theory of Computing at Berkeley.
I am on the advisory board for the Vienna Center for Logic and Algorithms.
I am on the steering committees for ICALP, LICS, WoLLIC, and LCC.
In 2014 and 2015, I served as chair of the jury for the ACM-India Doctoral Dissertation Award.
I served as principal organiser of the programme on Logic and Algorithms at the Isaac Newton Institute of Mathematical Sciences from 16 January to 7 July 2006. You can read the final report of the programme here.
Research Interests: 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, progam models, etc. Besides its connection to descriptive complexity, the subject has applications in database theory, verification and the analysis of games.
Papers: A list of selected publications, including some available
electronically is here.
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 of lecture courses for research students 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)
Editorial Work: I serve on the editorial board of:
ACM Transactions on Computational Logic
Computability
Journal of Computer and System Sciences
FoLLI LNCS series
and served for nine years as reviews editor of the
Meetings: Some conferences, workshops and the like I'm currently involved in.
- FSTTCS 2022 (Track B PC chair)
- FSTTCS 2021 (PC member)
- ICLA 2021 (PC member)
- Logic Colloquium 2021 (PC member)
- ICALP 2020 (Track B PC chair)
- LiCS 2020 (PC member)
- ICLA 2019 (PC member)
- LiCS 2018 (PC co-chair)
I was the principal local organiser of the Turing Centenary Conference: CiE 2012 - How the World Computes.
Teaching:
I am on sabbatical leave during Lent and Easter 2021.
Courses I have lectured in the past include:
- Complexity Theory for Part 1B students.
- Topics in Logic and Complexity for Part 3 and the MPhil ACS.
- Quantum Computing for Part 2 students.
- Computation 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.
MPhil ACS, Part III and Part II 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.
Last modified: 20 April 2021.