Computational Complexity
University of Amsterdam – February-March 2019

Lecturer: Ronald de Haan
Teaching assistant: Jan Czajkowski
Course catalogue.
Datanose

Lectures

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

Exercise session

Friday 13:00-15:00 (SP A1.04)

Textbook

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

Homework and exam

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.

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.  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
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
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
19 Mar.  15-17 SP G0.18B Lecture 12
21 Mar.  11-13 SP G0.18B Lecture 13
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.)
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.