Topics in Logic and Complexity

Lecture Recordings:

Recordings of lectures are available from Panopto

Lecture Note Handouts:

Handout 1
Handout 2
Handout 3
Handout 4
Handout 5

Reading List

Listed below are suggested readings from the following textbooks to accompany the lecture material.

1. C.H. Papadimitriou. Computational Complexity. Addison-Wesley. 1994.
2. S. Arora and B. Barak. Computational Complexity. Cambridge University Press. 2009.
3. H.-D. Ebbinghaus and J. Flum. Finite Model Theory (2nd ed.). Springer. 1999.
4. N. Immerman. Descriptive Complexity. Springer. 1999.
5. L. Libkin. Elements of Finite Model Theory. Springer. 2004.
6. E. Grädel et al. Finite Model Theory and its Applications. Springer. 2007.

• Lecture 1 and 2: Papadimitriou, Chapters 1 and 2; Arora-Barak, Chapter 1; Grädel et al. Chapter 1 (Weinstein); Arora-Barak, Chapters 2 and 4.
• Lecture 3 and 4: Papadimitriou, Chapters 8, 9 and Section 19.1; Libkin, Chapter 2; Immerman, Chapter 3.
• Lecture 5 and 6: Grädel et al. Sections 2.4, 3.1 and 3.2; Immerman, Chapter 7; Libkin, Section 9.2
• Lecture 7 and 8: Grädel et al. Sections 2.3; Ebbinghaus and Flum, Chapter 2; Libkin Chapters 3 and 4

Exercise Sheets:

Exercise Sheet 1
Exercise Sheet 2