skip to content

Department of Computer Science and Technology

  • Professor of Logic and Algorithms
  • Fellow of Robinson College
  • Fellow of the Alan Turing Institute

Biography

I 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.  I worked as a post-doctoral researcher and a lecturer at Swansea University before moving to Cambridge in 1999.  I have held visiting positions at Indiana University, Bloomington (USA), at INRIA and the University of Bordeaux (France) and at RWTH, Aachen (Germany). 

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, progam models, etc.  Besides its connection to descriptive complexity, the subject has applications in database theory, verification and the analysis of games.

Teaching

I am on sabbatical leave during Lent and Easter 2021.  Courses I have lectured in the past include:

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.

Professional Activities

I served on the the award committee for the EATCS and ACM SigACT Gödel Prize (chair in 2020). 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.  In 2014 and 2015, I served as chair of the jury for the ACM-India Doctoral Dissertation 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 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.

I am on the steering committees for LICS, ICALPWoLLIC, and  LCC.

I am on the advisory board for the Vienna Center for Logic and Algorithms.

I serve on the editorial board of: ACM Transactions on Computational LogicComputabilityJournal of Computer and System SciencesFoLLI LNCS series and served for nine years as reviews editor of the Bulletin of Symbolic Logic.

Publications

Here is the list of my papers at DBLP.

I regularly write reviews for Mathematical Reviews.

Contact Details

Room: 
FE20
Office phone: 
(01223) 3-34408
Email: 

anuj.dawarcl.cam.ac.uk