Course pages 2019–20
Topics in Logic and Complexity
Timetable:
Tue/Thu from Thu, 16 Jan. to Tue, 10 Mar. in FS07
Lecture Note Handouts:
Handout 1
Handout 2
Handout 3
Handout 4
Handout 5
Handout 6
Reading List
Listed below are suggested readings from the following textbooks to accompany the lecture material.
- C.H. Papadimitriou. Computational Complexity. Addison-Wesley. 1994.
- S. Arora and B. Barak. Computational Complexity. Cambridge University Press. 2009.
- H.-D. Ebbinghaus and J. Flum. Finite Model Theory (2nd ed.). Springer. 1999.
- N. Immerman. Descriptive Complexity. Springer. 1999.
- L. Libkin. Elements of Finite Model Theory. Springer. 2004.
- E. Grädel et al. Finite Model Theory and its Applications. Springer. 2007.
- Lecture 1: Papadimitriou, Chapters 1 and 2; Arora-Barak, Chapter 1; Grädel et al. Chapter 1 (Weinstein).
- Lecture 2: Papadimitriou, Chapters 7, 8 and 16; Arora-Barak, Chapters 2 and 4; Immerman, Chapter 2.
- Lecture 3: Papadimitriou, Chapter 8; Libkin, Chapter 2; Grädel et al, Sections 2.1-2.4 (Kolaitis).
- Lecture 4: Papadimitriou, Chapter 5 and Section 19.1; Grädel et al. Section 3.1.
- Lecture 5: Arora-Barak, Chapter 5; Grädel et al., Section 3.2; Libkin, Chapter 9; Ebbinghaus-Flum, Chapter 7.
- Lecture 6: Ebbinghaus-Flum, Chapter 2; Libkin, Chapter 3; Grädel et al., Section 2.3.
- Lecture 7: Ebbinghaus-Flum, Section 2.4; Libkin, Chapter 4; Grädel et al., Section 2.3 and 2.5 (Kolaitis).
- Lecture 8: Ebbinghaus-Flum, Section 8.1; Libkin, Sections 10.1 and 10.2; Grädel et al., Section 3.3 (Grädel).
- Lecture 9:Immerman, Chapter 4; Libkin, Sections 10.2 and 10.3; Grädel et al., Section 2.6 (Kolaitis).
- Lecture 10: Libkin, Chapter 10; Grädel et al., Section 3.3 (Grädel).
- Lecture 11: Ebbinghaus-Flum, Chapter 6; Libkin, Sections 6.6, 7.4 and 7.5.
Exercise Sheets: