Week |
Dates |
Lesson |
Remark |
I |
23 Feb. |
Lesson 0. Preliminaries |
-- |
II |
2 Mar. |
Lesson 1. The class NP |
-- |
III |
9 Mar. |
Lesson 2. The class NL |
HW1 |
IV |
16 Mar. |
Lesson 3. The class PSPACE |
-- |
V |
23 Mar. |
-- |
-- |
VI |
30 Mar. |
Lesson 4. Alternating Turing machines |
-- |
VII |
6 Apr. |
Holiday (Tomb sweeping festival) |
-- |
VIII |
13 Apr. |
Lesson 5. Polynomial hierarchy and the complexity classes for counting |
-- |
IX |
20 Apr. |
Lesson 6. Computing permanent |
HW 2 |
X |
27 Apr. |
Lesson 7. Boolean circuits part. I |
-- |
XI |
4 May |
Lesson 8. Boolean circuits part. II |
-- |
XII |
11 May |
Lesson 9. Probabilistic Turing machines |
HW 3 |
XIII |
18 May |
-- |
-- |
XIV |
25 May |
[Online] Lesson 10. The probabilistic method |
-- |
XV |
1 Jun. |
[Online] Lesson 11. Probabilistic reductions |
-- |
XVI |
8 Jun. |
[Online] Lesson 12. More on counting |
-- |
XVII |
15 Jun. |
[Online] Lesson 13. Interactive proofs |
-- |
XVIII |
22 Jun. |
-- |
-- |