Department of Computer Science and Technology

Topics in Logic and Complexity

Course pages 2022–23

# Topics in Logic and Complexity

The assessment for this module consists of an essay, worth 30% of the mark, and a take-home test

Essay

Essays are due in by noon on Friday, 10th March. The essay should be about 3000 words and describe a major result (or set of results) in the area of Logic and Complexity. It need not give a full proof, but should give enough context, including necessary definitions, to be able to state the results precisely and explain in general terms its significance. Some suggestions for topics are listed below, with some pointers to starting points of investigation. You may suggest your own, but you should in any case agree a topic with the lecturer at the latest by Friday, 3rd February.

1. Courcelle's Theorem.

2. Fixed-point Logic with Counting

These two papers offer an entry point into the literature: paper 1; paper 2. This is also covered in Libkin's book.

3. Parameterized Complexity of First-Order Logic.

You could start with this brief survey and follow the references: Algorithmic Meta-Theorems. Another useful source to consult is the book by Flum and Grohe on Parameterized Complexity Theory.

4. First-Order Logic and Constant-Depth Circuits

The basic relationship between the expressive power of first-order logic and families of constant-depth circuits is covered in depth in Immerman's book on Descriptive Complexity Theory. An account can also be found in Libkin's book (Sections 6.1-6.4), and follow the references therein.

5. Bulatov-Zhuk Theorem

In 2017, Bulatov and Zhuk independently resolved a 25-year old conjecture by Feder and Vardi on the complexity of constraint satisfaction problems. This conjecture, also known as the CSP dichotomy conjecture. A starting point of investigation might be this survey

6. Zero-One and Limit Laws

The zero-one law for first-order logic is one of the oldest results in finite model theory. Extensions of it have been established by considering stronger logic; varying probability distributions and limiting probabilities other than zero and one. An essay might cover some of these. The basics are covered in Chapter 12 of Libkin's book.

7. Abiteboul-Vianu Theorem

This is covered in some detail in Libkin's book (Chapter 11). So, an essay might cover some extensions of it, such as to logics with counting.

8. The Quest for a Logic for P

A start could be this brief survey by Grohe. Also refer to the final chapter of the book by Ebbinghaus and Flum.

9. Parity Games and Fixed-Point Logic

A starting point for the connection with logic could be this paper. Ideally an essay would also cover more recent complexity results about parity games and could also discuss relations to other games such as mean-payoff games and stochastic games. There is also basic information on wikipedia.

10. Proof Complexity

Another area where logic and complexity intersect, not much covered in this course is Proof Complexity. A starting point of investigation could be the book on the subject by Krajicek.

Test

The take-home test will take place between 14th and 18th March. It will consist of a collection of problems based on the material lectured. The problems will be of a style similar to those in the exercise sheets.