Lecturer: Ronald de Haan
Teaching assistant: Boas Kluiving
Course catalogue
Datanose
Canvas
Wednesday 17:00–19:00 (SP D1.112)
Thursday 17:00–19:00 (SP G2.02)
(There are a few exceptions. See the entries marked in red in the schedule below.)
Thursday 13:00–15:00 (SP D1.110)
Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak.
Homework exercises will generally be made available on Monday and have to be handed in on Monday one week later. Please hand in your solutions to the homework assignments via Canvas. You are allowed to cooperate, but everyone has to write down their solution in their own words. When computing the average grade for the exercises, the lowest score will be dropped.
Besides the exercises there will be a final exam. The exam will be open book, which means you are allowed to bring the book and any notes you made—digital equipment is not allowed. The final grade for the course will be the average of the grade for the exercises and the final exam.
(Entries marked in red are lectures that are exceptions to the regular days/locations.)
Time  Location  Topic 

5 Feb. 17–19  SP D1.112  Lecture 1: Introduction to computational complexity Book: 1.0–1.3, 1.6 Slides Handout For visualizations of Turing machines, you can visit https://turingmachinesimulator.com/ (the Turing machines shown there are bidirectional, see Claim 1.8 in the book). 
6 Feb. 13–15  SP D1.110  Exercise session on asymptotic notation, Turing machines Exercise sheet Book: 0.3, 1.1–1.2 
6 Feb. 17–19  SP G2.02  Lecture 2: P, NP, coNP, reductions Book: 1.4, 1.7, 2.0–2.2, 2.6 Handout 
Homework 1 (deadline: 17 Feb., 17:00)  
12 Feb. 17–19  SP D1.112  Lecture 3: NPcompleteness, CookLevin Theorem, search vs. decision problems Book: 2.3–2.5, 2.7 Handout 
13 Feb. 13–15  SP D1.110  Exercise session Exercise sheet 
14 Feb. 13–15  SP G3.02  Lecture 4: Diagonalization, time hierarchy theorems, Ladner's Theorem Book: 3.0–3.3 No handout 
Homework 2 (deadline: 24 Feb., 17:00)  
19 Feb. 17–19  SP D1.112  Lecture 5: Relativization, BakerGillSolovay Theorem Book: 3.4 Handout 
20 Feb. 13–15  SP D1.110  Exercise session Exercise sheet 
20 Feb. 17–19  SP G2.02  Lecture 6: Space complexity, PSPACE, L, NL Book: Chapter 4 Handout 
Homework 3 (deadline: 2 Mar., 17:00)  
26 Feb. 17–19  SP D1.112  Lecture 7: Polynomial Hierarchy Book: Chapter 5 Handout ('Parody news article' about the collapse of the PH) 
27 Feb. 13–15  SP D1.110  Exercise session Exercise sheet 
27 Feb. 17–19  SP G3.02  Lecture 8: Circuit complexity, KarpLipton Theorem Book: Chapter 6 Handout 
Homework 4 (deadline: 9 Mar., 17:00)  
4 Mar. 17–19  SP D1.112  Lecture 9: Probabilistic algorithms, BPP Book: 7.1–7.3 Handout 
5 Mar. 13–15  SP D1.110  Exercise session Exercise sheet 
5 Mar. 17–19  SP G2.02  Lecture 10: Approximation, PCP Theorem Book: 11.0–11.4 Handout 
Homework 5 (deadline: 16 Mar., 17:00)  
11 Mar. 17–19  SP D1.112  Lecture 11: Subexponentialtime complexity, Exponential Time Hypothesis 14.0–14.2 of the book Parameterized Algorithms, by Cygan et al. Handout 
12 Mar. 13–15  SP D1.110  Exercise session Exercise sheet 
13 Mar. 13–15  SP G3.02  Book: 8.1–8.3, 17.1–17.2, The Complexity Zoo 
Homework 6 (deadline: 23 Mar., 17:00)  
18 Mar. 17–19  on Zoom  Lecture 13: Averagecase complexity and Impagliazzo's Five Worlds Book: 9.0, 9.2, 18.0–18.2, 18.4 Slides 
19 Mar. 13–15  
20 Mar. 13–15  on Zoom  Lecture 14: Recap and question session Slides 
24 Mar. 9–12  Instead of the inclass exam, we will have a takehome exam that is due on 31. Mar. at 17:00. Takehome exam 

22 Jun. 9–12  SP A1.12  Resit exam (You are allowed to bring the book and notes, but no electronic devices.) Send an email if you would like to participate in the resit exam. 