Lecturer: Ronald de Haan
Teaching assistants: Wouter Vromen & Hannah Van Santvliet
Course catalogue
Datanose
Canvas
Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak.
Thursday 15:00–17:00 (SP A1.28)
Friday 15:00–17:00 (SP A1.04)
(Exceptions are indicated in red in the schedule below.)
Wednesday 13:00–15:00 (SP G0.05)
(Cartoon by Stefan Szeider—based on the original cartoon from the book Computers and Intractability: A Guide to the Theory of NPCompleteness (1979) by Michael Garey and David S. Johnson.)
Homework exercises will generally be made available on Tuesdays and have to be handed in on Tuesday one week later. Please hand in your solutions to the homework assignments via Canvas.
Besides the exercises there will be a takehome final exam. The exam will be open book, which means you are allowed to use the book and any notes you made.
The final grade for the course will be the average of the grade for the exercises and the final exam.
Time  Location  Topic 

Wed 3 Apr. 13–15  SP G0.05  Exercise session 1
Exercise sheet Book: 0.3, 1.1–1.3, 1.6 Preparatory slides 
Thu 4 Apr. 15–17  SP A1.28  Lecture 1: Introduction to computational complexity,
P, NP, coNP, reductions Book: 1.0–1.3, 1.6–1.7, 2.0–2.2, 2.6 Slides 
Fri 5 Apr. 15–17  SP A1.04  Lecture 2: NPcompleteness, CookLevin Theorem, search vs. decision problems Book: 2.3–2.5, 2.7 Slides 
Homework 1 Due: Tue 16 Apr., 23:59 Use this template (pdf) for typesetting Slitherlink gadgets. 

Wed 10 Apr. 13–15  SP G0.05  Exercise session 2
Exercise sheet 
Thu 11 Apr. 15–17  SP A1.28  Lecture 3: Diagonalization, time hierarchy theorems, Ladner's Theorem Book: 1.4–1.5, 3.0–3.3 Slides 
Fri 12 Apr. 15–17  SP A1.04  Lecture 4: Relativization, BakerGillSolovay Theorem Book: 3.4 Slides 
Wed 17 Apr. 13–15  SP G0.05  Exercise session 3
Exercise sheet 
Thu 18 Apr. 15–17  SP A1.28  Lecture 5: Space complexity, PSPACE, L, NL Book: Chapter 4 Slides 
Fri 19 Apr. 15–17  SP A1.04  Lecture 6: Polynomial Hierarchy Book: Chapter 5 ('Parody news article' about the collapse of the PH) Slides 
Homework 2 Due: Tue 7 May, 23:59 

Tue 23 Apr. 11–13  SP A1.28  Lecture 7: Circuit complexity, KarpLipton Theorem Book: Chapter 6 Slides 
Wed 24 Apr. 13–15  SP G0.05  Exercise session 4
Exercise sheet 
Thu 25 Apr. 15–17  SP A1.28  Lecture 8: Recap and question session
Slides 
Mon 6 May 11–13  SP A1.28  Lecture 9: Probabilistic algorithms, BPP Book: 7.1–7.3 
Homework 3 Available on: Tue 7 May Due: Tue 14 May, 23:59 

Tue 7 May 11–13  SP G2.10  Lecture 10: Approximation, PCP Theorem Book: 11.0–11.4 
Wed 8 May 13–15  SP G0.05  Exercise session 5

Wed 15 May 13–15  SP G0.05  Exercise session 6 
Thu 16 May 15–17  SP A1.28  Lecture 11: Subexponentialtime complexity, Exponential Time Hypothesis 14.0–14.2 of the book Parameterized Algorithms, by Cygan et al. 
Tue 21 May 11–13  SP G0.10–G0.12  Lecture 12: Averagecase complexity and Impagliazzo's Five Worlds Book: 9.0, 9.2, 18.0–18.2, 18.4 
Wed 22 May 13–15  SP G0.05  Exercise session 7 
Thu 23 May 15–17  SP A1.28  Lecture 13: Meta complexity, MCSP 
Fri 24 May 15–17  SP A1.04  Lecture 14: Recap and question session 
Final takehome exam
(Due: Fri 31 May, 23:59) Exams from previous years can be used as practice exams: 2020, 2021, 2023. 