| Week |
Dates |
Lesson |
Remark |
|
| I |
24 Feb. |
Lesson 1. Basic complexity classes
(note-01.tex, note-01.pdf) |
-- |
| II |
3 Mar. |
Lesson 2. NP-complete problems.
(note-02.tex, note-02.pdf) |
HW 1 out.
(hw-01.pdf) |
| III |
10 Mar. |
Lesson 3. More on the class NP.
(note-03.tex, note-03.pdf) |
-- |
| IV |
17 Mar. |
No lesson. |
-- |
| V |
24 Mar. |
Lesson 4. The class NL and PSPACE.
(note-04.tex, note-04.pdf) |
-- |
| VI |
31 Mar. |
Lesson 5. Alternating Turing machines.
(note-05.tex, note-05.pdf) |
HW 2 out.
(hw-02.pdf) |
| VII |
7 Apr. |
Lesson 6. The class #P.
(note-06.tex, note-06.pdf) |
-- |
| VIII |
14 Apr. |
Lesson 7. Boolean circuits.
(note-07.tex, note-07.pdf) |
-- |
| IX |
21 Apr. |
Lesson 8. Probabilistic Turing machines.
(note-08.tex, note-08.pdf) |
-- |
| X |
28 Apr. |
No lesson. |
-- |
| XI |
5 May. |
Lesson 9. Probabilistic reductions
(note-09.tex, note-09.pdf) |
-- |
| XII |
12 May |
Lesson 10. Toda's theorem.
(note-10.tex, note-10.pdf) |
-- |
| XIII |
19 May |
Lesson 11. Interactive proofs.
(note-11.tex, note-11.pdf) |
HW 3 out.
(hw-03.pdf) |
| XIV |
26 May |
Lesson 12. IP and PSPACE
(note-12.tex, note-12.pdf) |
-- |
| XV |
2 Jun. |
(Make-up) Lesson 6. The class #P.
(note-06.tex, note-06.pdf) |
-- |
| XVI |
9 Jun. |
Lesson 13. Probabilistic checkable proofs |
-- |