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
• Lecture 9 and 10: Libkin, Section 7.1-7.3; Ebbinghaus and Flum, Section 3.1; Grädel et al., Section 2.6 and 3.3.
• Lecture 11 and 12: Immerman, Chapter 4 and Section 9.1., Libkin Chapter 10
• Lecture 13 and 14: Grädel et al., Chapter 6.

Exercise Sheets:

Exercise Sheet 1
Exercise Sheet 2