skip to primary navigationskip to content

Department of Computer Science and Technology



Course pages 2023–24

Topics in Logic and Complexity

Principal lecturer: Prof Anuj Dawar
Taken by: MPhil ACS, Part III
Code: L15
Term: Lent
Hours: 16
Format: In-person lectures
Class limit: max. 20 students
Prerequisites: Undergraduate courses in complexity theory, computation theory and first-order logic
Moodle, timetable


This module aims to provide an introduction to topics in complexity theory beyond that covered in the undergraduate course and a grounding in research that connects this with methods from logic. The topics covered in the last four lectures will focus on current research and may vary from year to year.


  • Complexity theory—a review of the major complexity classes (space, time, nondeterministic, etc.) and their interrelationships. [3 lectures]
  • First-order and second-order logic: their expressive power and computational complexity. [3 lectures]
  • Lower bounds on expressive power: the use of games and locality. [3 lectures]
  • Fixed-point logics and descriptive complexity. [3 lectures]
  • A selection of topics from the following [4 lectures]:
    • finite-variable logics;
    • complexity of constraint satisfaction problems;
    • random structures;
    • parameterized complexity;
    • complexity of logical theories;
    • logic and circuit complexity;
    • logics of polynomial time computation;
    • proof complexity.


On completion of this module, students should:

  • be familiar with the basic relationship between the expressive power of logic and computational complexity;
  • be able to formulate simple game-based inexpressibility arguments;
  • be able to identify current research issues relating logic to complexity.

Coursework and practical work



The assessment will be based on an essay completed during the term, and a take-home test taken after the course, weighted as follows:

  • Essay: 30%
  • Take-home Test: 70%

Recommended reading

Arora, S. and Barak, B. (2009). Computational complexity. Cambridge University Press.
Gradel. E. et al. (2007). Finite model theory and its applications. Springer.
Libkin, L. (2004). Elements of finite model theory. Springer.
Immerman, N. (1999). Descriptive complexity. Springer.
Ebbinghaus, H-D. and Flum, J. (1999). Finite model theory. Springer.