Computational Complexity
University of Amsterdam, February–March 2021
Lecturer: Ronald de Haan
Teaching assistant: Simon Rey
Course catalogue
Datanose
Canvas
Lectures
Monday 15:00–17:00 (online; Zoom link available on Canvas)
Friday 9:00–11:00 (online; Zoom link available on Canvas)
Exercise session
Thursday 13:00–15:00 (online; Zoom link available on Canvas)
Textbook
Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak.
(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 Mondays and have to be handed in on Monday one week later, before the start of the lecture. Please hand in your solutions to the homework assignments via Canvas. When computing the average grade for the exercises, the lowest score will be dropped.
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 |
|---|---|---|
| 1 Feb. 15–17 | online | Lecture 1: Introduction to computational complexity Book: 1.0–1.3, 1.6 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). Slides |
| 4 Feb. 13–15 | online | Exercise session on asymptotic notation, Turing machines Exercise sheet Book: 0.3, 1.1–1.3, 1.6 |
| 5 Feb. 9–11 | online | Lecture 2: P, NP, coNP, reductions Book: 1.4, 1.7, 2.0–2.2, 2.6 Slides |
| 8 Feb. 15–17 | online | Lecture 3: NP-completeness, Cook-Levin Theorem, search vs. decision problems Book: 2.3–2.5, 2.7 Slides |
| Homework 1 (due at: 15 Feb., 15:00) Use this template (pdf) for typesetting Slitherlink gadgets. |
||
| 11 Feb. 13–15 | online | Exercise session Exercise sheet |
| 12 Feb. 9–11 | online | Lecture 4: Diagonalization, time hierarchy theorems, Ladner's Theorem Book: 3.0–3.3 Slides |
| 15 Feb. 15–17 | online | Lecture 5: Relativization, Baker-Gill-Solovay Theorem Book: 3.4 Slides |
| Homework 2 (due at: 22 Feb., 13:00) | ||
| 18 Feb. 13–15 | online | Exercise session Exercise sheet |
| 19 Feb. 9–11 | online | Lecture 6: Space complexity, PSPACE, L, NL Book: Chapter 4 Slides |
| 22 Feb. 15–17 | online | Lecture 7: Polynomial Hierarchy Book: Chapter 5 ('Parody news article' about the collapse of the PH) Slides |
| Homework 3 (due at: 1 Mar., 13:00) | ||
| 25 Feb. 13–15 | online | Exercise session Exercise sheet |
| 26 Feb. 9–11 | online | Lecture 8: Recap and question session Slides (annotated) |
| 1 Mar. 15–17 | online | Lecture 9: Circuit complexity, Karp-Lipton Theorem Book: Chapter 6 Slides |
| Homework 4 (due at: 8 Mar., 13:00) | ||
| 4 Mar. 13–15 | online | Exercise session Exercise sheet |
| 5 Mar. 9–11 | online | Lecture 10: Probabilistic algorithms, BPP Book: 7.1–7.3 Slides |
| 8 Mar. 15–17 | online | Lecture 11: Approximation, PCP Theorem Book: 11.0–11.4 Slides |
| Homework 5 (due at: 15 Mar., 13:00) | ||
| 11 Mar. 13–15 | online | Exercise session Exercise sheet |
| 12 Mar. 9–11 | online | Lecture 12: Subexponential-time complexity, Exponential Time Hypothesis 14.0–14.2 of the book Parameterized Algorithms, by Cygan et al. Slides |
| 15 Mar. 15–17 | online | Lecture 13: Average-case complexity and Impagliazzo's Five Worlds Book: 9.0, 9.2, 18.0–18.2, 18.4 Slides (Impagliazzo's paper) |
| 18 Mar. 13–15 | online | Exercise session Exercise sheet |
| 19 Mar. 9–11 | online | Lecture 14: Recap and question session Slides |
| Final take-home exam (Due at 29 Mar., 17:00) Last year's exam can be used as practice exam. |