Computational Complexity
University of Amsterdam, April–May 2024
Lecturer: Ronald de Haan
Teaching assistants: Wouter Vromen & Hannah Van Santvliet
Course catalogue
Datanose
Canvas
Textbook
Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak.
Lectures
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.)
Exercise session
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 NP-Completeness (1979) by Michael Garey and David S. Johnson.)
Homework and exam
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 take-home 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.
Schedule
| 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: NP-completeness, Cook-Levin 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, Baker-Gill-Solovay 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, Karp-Lipton 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 Proof to discuss |
| 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: Subexponential-time 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: Average-case 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 take-home exam
(Due: Fri 31 May, 23:59) Exams from previous years can be used as practice exams: 2020, 2021, 2023. |