Lecturer: Ronald de Haan
Teaching assistant: Jan Czajkowski
Course catalogue.
Datanose
Note: this is the course web page for 2019. For the most recent edition of the course, please visit the corresponding course page.
Tuesday 15:00-17:00 (SP G0.18B)
Thursday 11:00-13:00 (SP G0.18B)
(There are a few exceptions. See the entries marked in red in the schedule below.)
Friday 13:00-15:00 (SP A1.04)
Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak.
Homework exercises will generally be handed out on Wednesday and have to be handed in on Wednesday one week later. Handing in via email to Jan Czajkowski is encouraged. 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. 15-17 | SP G0.18B | Lecture 1: Introduction to computational complexity Book: 1.0–1.3, 1.6 Slides 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). |
| Homework 1 (deadline: 13 Feb., 17:00) | ||
| 7 Feb. 11-13 | No lecture! | |
| 8 Feb. 13-15 | SP A1.04 | Exercise session on asymptotic notation, Turing machines Exercise sheet Book: 0.3, 1.1–1.2 |
| 12 Feb. 15-17 | SP G0.18B | Lecture 2: P, NP, coNP, reductions Book: 1.4, 1.7, 2.0–2.2, 2.6 |
| Homework 2 (deadline: 20 Feb., 17:00) | ||
| 14 Feb. 11-13 | SP G0.18B | Lecture 3: NP-completeness, Cook-Levin Theorem, search vs. decision problems Book: 2.3–2.5, 2.7 |
| 15 Feb. 13-15 | SP A1.04 | Exercise session Exercise sheet |
| 19 Feb. 15-17 | SP G0.18B | Lecture 4: Diagonalization, time hierarchy theorems, Ladner's Theorem Book: 3.0–3.3 |
| Homework 3 (deadline: 27 Feb., 17:00) | ||
| 21 Feb. 11-13 | SP G0.18B | Lecture 5: Relativization, Baker-Gill-Solovay Theorem Book: 3.4 |
| 22 Feb. 13-15 | SP A1.04 | Exercise session Exercise sheet |
| 26 Feb. 15-17 | SP G0.18B | Lecture 6: Space complexity, PSPACE, L, NL Book: Chapter 4 |
| Homework 4 (deadline: 6 Mar., 17:00) | ||
| 28 Feb. 11-13 | SP G0.18B | Lecture 7: Polynomial Hierarchy Book: Chapter 5 |
| 1 Mar. 13-15 | SP A1.04 | Exercise session Exercise sheet |
| 5 Mar. 15-17 | SP G0.18B | Lecture 8: Circuit complexity, Karp-Lipton Theorem Book: Chapter 6 |
| Homework 5 (deadline: 13 Mar., 17:00) | ||
| 7 Mar. 11-13 | SP G0.05 | Lecture 9: Probabilistic algorithms, BPP Book: 7.1–7.3 |
| 8 Mar. 13-15 | SP A1.04 | Exercise session Exercise sheet |
| 12 Mar. 15-17 | SP G0.18B | Lecture 10: Approximation, PCP Theorem Book: 11.0–11.4 |
| Homework 6 (deadline: 20 Mar., 17:00) | ||
| 14 Mar. 11-13 | SP G0.05 | Lecture 11: Subexponential-time complexity, Exponential Time Hypothesis 14.0–14.2 of the book Parameterized Algorithms, by Cygan et al. |
| 15 Mar. 13-15 | SP A1.04 | Exercise session Exercise sheet |
| 19 Mar. 15-17 | SP G0.18B | Lecture 12: A visit to the Complexity Zoo Book: 8.1-8.3, 17.1-17.2, The Complexity Zoo |
| 21 Mar. 11-13 | SP G0.18B | Lecture 13: Average-case complexity and Impagliazzo's Five Worlds Book: 9.0, 9.2, 18.0–18.2, 18.4 |
| 22 Mar. 13-15 | SP A1.04 | Exercise session |
| 26 Mar. 9-12 | REC A1.02 | Final exam (You are allowed to bring the book and notes, but no electronic devices.) Practice exam |
| 24 Jun. 13-16 | SP G3.05 | 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. |