skip to primary navigationskip to content

Department of Computer Science and Technology

Masters

 

Course pages 2022–23

Topics in Logic and Complexity

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

Aims

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.

Syllabus

  • 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.

Objectives

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

None.

Assessment

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%
  • 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.

Further Information

Due to infectious respiratory diseases, the method of teaching for this module may be adjusted to cater for physical distancing and students who are working remotely. Unless otherwise advised, this module will be taught in person.