Mastermath course Complexity Theory, Spring 2011

Lecturers: Krzysztof Pietrzak and Sebastiaan Terwijn.
For information about the course see the Mastermath webpage.
On this page we list the material treated so far. (Lecturer indicated by S or K.)
"course notes" refers to these Complexity Theory notes, available as [postscript] or [pdf]
AB denotes the book by Arora and Barak.

 Feb. 08 S. Preliminaries. Sections 2.1, 2.2, 2.4, 2.5 from course notes. Feb. 15 K. Sections 3.1, 3.2 from course notes. NP-completeness Hamilton path from AB (p53). Exercises: NP is closed under union and intersection. Reductions: 3SAT is NP-complete. Ex 3.5.14. Feb. 22 S. Sections 3.3, 4.1, 4.2 from course notes. Exercises: 4.4.4, 4.4.5, 4.4.6, 4.4.1, 4.4.2 Mar. 01 S. Sections 2.3, 5.1, 5.2 from course notes. Exercises: 5.7.1, 5.7.2, 2.7.11, 3.5.9. Mar. 08 NO LECTURE Mar. 15 S. Sections 4.3, 5.3, 5.6 from course notes. Exercises: 4.4.7, 4.4.8, 5.7.11, 5.7.12, 5.7.3. Mar. 22 K. From AB: Definition 7.1 (PTM) Definition 7.2 (BPP) & Def. 7.3 (BPP, altenative Def.) Section 7.2 (Examples) 7.2.1 Finding a median, 7.2.2 Primality & 7.2.3 Polynomial Identity testing. Section 7.3 RP, ZPP. 7.5.1 Theorem 7.14: BPP in P/poly. 7.5.2 Theorem 7.15: BPP in Sigma_2^p. Exercises: course notes: 6.5.8, 6.5.10 von Neumann trick Lemma 7.13 AB, Error amplification for RP Mar. 29 K. Note the change of room C1.112. #P is in IP, and IP=PSPACE from Thomas Holenstein's lecture at ETH. Apr. 05 K. Sections 9.1-9.3 from AB. (Theorem 9.12, Goldreich-Levin Theorem.) Exercises: 9.5 , 9.11 and 9.12 from AB. Apr. 12 K. 9.4 from AB (definition of ZK and graph-isomorphism in perfect ZK) NP is in computational ZK by showing that graph 3-coloring is in CZK. (Extra material, not for exam.) Exercise: to find out a CZK proof showing that a graph has a Hamiltonian cycle. Apr. 19 S. Sections 7.1-7.4 from course notes. Exercises: 7.6.1, 7.6.2, 7.6.3, 7.6.4. Apr. 26 K. Sections 10.1-10.3 from course notes. Exercises: 10.5.1 and 10.5.5. May 03 NO LECTURE May 10 K. Sections 10.3 and 10.4 from course notes. Exercises 10.5.1, 10.5.2, 10.5.4 May 17 S. Sections 2.6 and 7.5 from course notes. Exercises 7.6.6, 7.6.7, 7.6.8 (difficult), 7.6.9. May 24 NO LECTURE June 14 Exam. Time: 13:00-16:00. Room: C0.110