Wednesday 11:00-13:00 (SP G2.02)
Friday 11:00-13:00 (SP F2.04)
The first lecture is on Friday February 9 at 11:00 in room SP F2.04.
(There are a few exceptions. See the entries marked in red in the schedule below.)
Friday 15:00-17:00 (SP G0.05)
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.)
|9 Feb. 11-13||SP F2.04||Lecture 1: Introduction to computational complexity
Book: 1.0–1.3, 1.6
Homework 1 (deadline: 14 Feb. 11:00)
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).
|9 Feb. 15-17||SP G0.05||Exercise session on asymptotic notation, Turing machines
Book: 0.3, 1.1–1.2
|14 Feb. 11-13||SP G2.02||Lecture 2: P, NP, coNP, reductions
Book: 1.4, 1.7, 2.0–2.2, 2.6
Homework 2 (deadline: 21 Feb. 11:00), typos fixed on 19 Feb.
|15 Feb. 9-11||SP D1.114||Lecture 3: NP-completeness, Cook-Levin Theorem, search vs. decision problems
Book: 2.3–2.5, 2.7
|16 Feb. 11-13||SP F2.04||Lecture 4: Diagonalization, time hierarchy theorems, Ladner's Theorem
|16 Feb. 15-17||SP G0.05||Exercise session on homework 1|
|21 Feb. 11-13||SP G2.02||Lecture 5: Relativization, Baker-Gill-Solovay Theorem
Homework 3 (deadline: 28 Feb. 23:59)
|23 Feb. 11-13||SP F2.04||Lecture 6: Space complexity, PSPACE, L, NL
Book: Chapter 4
|23 Feb. 15-17||SP G0.05||Exercise session on homework 2|
|28 Feb. 11-13||SP G2.02||Lecture 7: Polynomial Hierarchy
Book: Chapter 5
Homework 4 (deadline: 7 Mar. 23:59)
|2 Mar. 11-13||SP F2.04||Lecture 8: Circuit complexity, Karp-Lipton Theorem
Book: Chapter 6
|2 Mar. 15-17||SP G0.05||Exercise session on homework 3|
|6 Mar. 11-13||SP G5.29||Lecture 9: Probabilistic algorithms, BPP
Homework 5 (deadline: 14 Mar. 23:59)
|7 Mar. 11-13||-||No lecture|
|9 Mar. 11-13||SP F2.04||Lecture 10: Approximation, PCP Theorem
|9 Mar. 15-17||SP G0.05||Exercise session on homework 4|
|14 Mar. 11-13||SP G2.02||Lecture 11: Subexponential-time complexity, Exponential Time Hypothesis
14.0–14.2 of the book Parameterized Algorithms, by Cygan et al.
Homework 6 (deadline: 21 Mar. 23:59), updated on 20 Mar.
|16 Mar. 11-13||SP F2.04||Lecture 12: Interactive proofs, graph isomorphism problem
|16 Mar. 15-17||SP G0.05||Exercise session on homework 5|
|21 Mar. 11-13||SP G2.02||Lecture 13: IP = PSPACE
|23 Mar. 11-13||SP F2.04||Lecture 14: Impagliazzo's Five Worlds
Book: 9.0, 9.2, 18.0–18.2, 18.4
|23 Mar. 15-17||SP G0.05||Exercise session on homework 6|
|28 Mar. 9-12||SP G4.15||Final exam
(You are allowed to bring the book and notes, but no electronic devices.)