Computational Complexity
University of Amsterdam, February–March 2020

Lecturer: Ronald de Haan
Teaching assistant: Boas Kluiving
Course catalogue
Datanose
Canvas

Note: this is the course web page for 2020. For the most recent edition of the course, please visit the corresponding course page.

News

Lectures

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

Exercise session

Thursday 13:00–15:00 (SP D1.110)

Textbook

Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak.

Homework and exam

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.

Schedule

(Entries marked in red are lectures that are exceptions to the regular days/locations.)

TimeLocationTopic
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: NP-completeness, Cook-Levin 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, Baker-Gill-Solovay 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, Karp-Lipton 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: Subexponential-time 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 Lecture 12: A visit to the Complexity Zoo Cancelled due to the coronavirus outbreak!
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: Average-case complexity and Impagliazzo's Five Worlds
Book: 9.0, 9.2, 18.0–18.2, 18.4
Slides
19 Mar.  13–15 SP D1.110 Exercise session Cancelled due to the coronavirus outbreak!
20 Mar.  13–15 on Zoom Lecture 14: Recap and question session
Slides
24 Mar.  9–12 SP C0.110 Final exam The in-class exam is cancelled due to the coronavirus outbreak.
Instead of the in-class exam, we will have a take-home exam that is due on 31. Mar. at 17:00.
Take-home 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.