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

Time	Location	Topic
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.