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 |
|