| Week |
Dates |
Lesson |
Remark |
|
| I |
14 Feb. |
Lesson 0a. Preliminaries
(note-00.tex, note-00.pdf) |
-- |
| II |
21 Feb. |
Lesson 0b. Review on Cook-Levin reductions.
| -- |
| III |
28 Feb. |
Holiday (Peace memorial day) |
-- |
| IV |
7 Mar. |
Lesson 1. The class NP
(note-01.tex, note-01.pdf) |
HW 1: hw-01.tex, hw-01.pdf |
| V |
14 Mar. |
Lesson 2. The class NL and PSPACE
(note-02.tex, note-02.pdf) |
-- |
| VI |
21 Mar. |
Lesson 3. Alternating Turing machines
(note-03.tex, note-03.pdf) |
-- |
| VII |
28 Mar. |
Lesson 4. The polynomial hierarchy
(note-04.tex, note-04.pdf) |
HW 2: hw-02.tex, hw-02.pdf |
| VIII |
4 Apr. |
Holiday (Children's day) |
-- |
| IX |
11 Apr. |
Lesson 5. The class #P
(note-05.tex, note-05.pdf) |
-- |
| X |
18 Apr. |
Lesson 6. Boolean circuits
(note-06.tex, note-06.pdf) |
-- |
| XI |
25 Apr. |
Lesson 7. Probabilistic algorithms
(note-07.tex, note-07.pdf) |
HW 2 due. |
| XII |
2 May |
Lesson 8. Probabilistic reductions
(note-08.tex, note-08.pdf) |
HW 3: hw-03.tex, hw-03.pdf |
| XIII |
9 May |
Lesson 9. Toda's theorem
(note-09.tex, note-09.pdf) |
-- |
| XIV |
16 May |
Lesson 10. Interactive proofs
(note-10.tex, note-10.pdf) |
-- |
| XV |
23 May |
Lesson 11. IP = PSPACE
(note-11.tex, note-11.pdf) |
-- |
| XVI |
30 May |
-- |
HW 3 due. |