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