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. NPcompleteness
Hamilton path from AB (p53).
Exercises: NP is closed under union and intersection.
Reductions: 3SAT is NPcomplete.
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.19.3 from AB.
(Theorem 9.12, GoldreichLevin Theorem.)
Exercises: 9.5 , 9.11 and 9.12 from AB.

Apr. 12 K. 
9.4 from AB (definition of ZK and graphisomorphism in perfect ZK)
NP is in computational ZK by showing that graph 3coloring 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.17.4 from course notes.
Exercises: 7.6.1, 7.6.2, 7.6.3, 7.6.4.

Apr. 26 K. 
Sections 10.110.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:0016:00. Room: C0.110 
