skip to primary navigationskip to content
 

Course pages 2021–22

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.

  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: 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:

Exercise Sheet 1
Exercise Sheet 2