skip to primary navigationskip to content
 

Course pages 2021–22

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, 18th 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, 28th January.

  1. Courcelle's Theorem.

    You could start with the entry in Wikipedia: 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

  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.

Test

The take-home test will take place between 28th April and 2nd May. 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.