Computer Laboratory

Course pages 2011–12

Topics in Logic and Complexity

Principal lecturer: Prof Anuj Dawar
Taken by: MPhil ACS, Part III
Code: L15
Hours: 16
Prerequisites: Undergraduate courses in complexity theory, computation theory and first-order logic

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 lecture syllabus will be assessed by a take-home test, set and marked by the principal lecturer.

The final module mark will be expressed as a percentage.

Recommended reading

Arora, S. & 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. & Flum, J. (1999). Finite model theory. Springer.