Topics in Logic and Complexity
Timetable:
Thu 20 Jan: 11.00-12.00
Tue 25 Jan and Thu 27 Jan: 11.00-13.00
Tue 15 Feb and Thu 17 Feb: 11.00-13.00
Tue/Thu from 22 Feb to 15 Mar: 11.00-12.00
Lecture 1 (20 Jan) and Lecture 10 (24 Feb) will be live streamed at the following Zoom link:
Meeting
ID: 984 1385 5204; Passcode: 833136
Recordings of Lecture 1 and Lectures 6-10 are available on the "Recordings"
Tab on this page
Recordings of lectures from Lecture 2 to Lecture 5 and Lecture 11 to
Lecture 12 are available at:
this
link.
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).
- Lectures 2 and 3: Arora-Barak, Chapters 2 and 4; Immerman, Chapter 2; Papadimitriou, Chapters 8, 9, and 16.
- Lectures 4 and 5: Libkin, Chapter 2; Grädel et al. Sections 2.4 and 3.1; Immerman, Chapter 3, Papadimitriou, Section 19.1
- Lecture 6: Grädel et al., Section 3.2; Papadimitriou, Section 8.3; Libkin, Section 9.2, Ebbinghaus and Flum, Chapter 7.
- Lecture 7: Ebbinghaus and Flum, Section 2.1-2.3; Libkin, Chapter 3; Grädel et al., Section 2.3.
- Lecture 8: Libkin, Chapter 4; Ebbinghaus and Flum, Section 2.4.
- Lecture 9: Libkin, Section 7.1-7.3; Ebbinghaus and Flum, Section 3.1
- Lecture 10: Grädel et al., Section 2.6; Ebbinghaus and Flum, Section 8.1; Libkin, Sections 10.1 and 10.2.
- Lecture 11 and 12: Grädel et al., Section 3.3; Libkin, Chapter 10.
- Lecture 13 and 14: Grädel et al., Chapter 6.
Exercise Sheets: