Computational Complexity
University of Amsterdam – September 2015

Lecturer: Harry Buhrman
Teaching assistant: Jeroen Zuiddam
Course catalogue
Datanose

Lectures

Tuesday 9:00-11:00
Thursday 11:00-13:00

Exercise session

Thursday 10:00-11:00

For location see Datanose. The first lecture is on Tuesday, September 1 at 9:00 am in room SP A1.04.

Textbook

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

Homework and exam

Exercises will be handed out on Thursday and have to be handed in on Thursday one week later. 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 between the grade for the exercises and the final exam.

If you want to take the resit exam, please send an email to Jeroen Zuiddam.

Schedule

TimeLocationTopic
1 Sep.  9-11 SP904 A1.04 Introduction to computational complexity
Slides
Homework 1, due 8 Sep. 9:00 am. Handing in via email is encouraged.
3 Sep.  10-11 SP904 G3.02 Exercise session on asymptotic notations.
Exercises, solutions
Book: 0.3
3 Sep.  11-13 SP904 C1.112 P, NP, reductions, co-NP
Book: 1.1–1.4, 1.6, 1.7, 2.1, 2.2
8 Sep.  9-11 SP904 A1.04 Cook-Levin Thm: 3-SAT is NP-complete, Decision vs Search
Book: 2.3, 2.5
Homework 2 (updated 15 Sep.), due Thursday 17 Sep. 10:00 am.
10 Sep.  10-11 SP123 CWI L016 Exercise session on homework.
10 Sep.  11-13 SP123 CWI L016 Diagonalization, time hierarchies
Book: 3.1, 3.2
15 Sep.  9-11 SP904 A1.04 Relativization
Book: 3.4
17 Sep.  10-11 SP904 G2.02 Exercise session on homework 2.
Homework 3 (updated 22 Sep.), due Thursday 24 Sep. 10:00 am.
17 Sep.  11-13 SP904 B0.201 Space complexity, PSPACE, L, NL
Book: Chapter 4
22 Sep.  9-11 SP904 G3.02 Immerman-Szelepcsényi theorem, the polynomial hierarchy
Book: 4.3.2, Chapter 5
24 Sep.  10-11 SP904 G0.05 Exercise session on homework 3.
Homework 4, due Thursday 1 Oct. 11:00 am.
24 Sep.  11-13 SP904 G5.29 Circuit complexity, the Karp-Lipton Theorem
Book: Chapter 6
29 Sep.  9-11 SP904 A1.04 Parity not in AC^0
Book: 14.2
1 Oct.  9-11 SP123 CWI L016 Probabilistic algorithms
Book: 7.1–7.3
1 Oct.  10-11 SP123 CWI L016 Exercise session on homework 4.
Homework 5, due Thursday 8 Oct. 10:00 am.
6 Oct.  9-11 SP904 A1.04 BPP, circuits and polynomial hierarchy
Book: 7.3–7.5
8 Oct.  10-11 SP904 G3.02 Exercise session on homework 5.
Homework 6, due Thursday 15 Oct. 10:00 am.
8 Oct.  11-13 SP904 G4.15 Interactive proofs, Graph-Isomorphism problem
Book: 8.1–8.2
13 Oct.  9-11 SP904 A1.04 IP = PSPACE
Book: 8.3
15 Oct.  10-11 SP123 CWI L016 Exercise session on homework 6.
15 Oct.  11-13 No lecture
19 Oct.  11-13 SP123 CWI L016 Question session
Homework 6 will have been graded.
21 Oct.  9-12 SP912 H0.08 Exam
You are allowed to bring books and notes, but no electronic devices.
Old exam
5 Jan.  18-21 SP904 D1.160 Resit exam
Please register by sending an email to Jeroen Zuiddam.

See also the website of the 2013/2014 course.