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

TimeLocationTopic
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
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.