|
|
|
|
|
|
|
|
|
|
|
Slides
- Lecture 1: slides [PDF]
- Lecture 2: slides [PDF]
- Lecture 3: slides [PDF]
- Lecture 4: slides [PDF]
- Lecture 5: slides [PDF]
- Lecture 6: slides [PDF]
- Lecture 7: slides [PDF]
- Lecture 8: slides [PDF]
- Lecture 9: slides [PDF], for proof of NL=coNL see also p.355-356 of Sipser,
proof of the general Immerman-Szelepcsenyi theorem, or the
original proof,
proof from the script of another course (pages 86-88)
- Lecture 10: slides [PDF]
- Lecture 10-Part II: slides [PDF]
- Lecture 11: slides [PDF], for construction of oracle X see p.378-379 of Sipser
- Lecture 12-13: slides [PDF],
notes on primality testing (contains also some nice slides summarizing the
definitions of RP, coRP, ZP, PP, BPP, and the known relationships between them)
- Lecture 14: slides [PDF]
- Lecture 15: slides [PDF]
- Lecture 16: slides [PDF]
- Lecture 17: slides [PDF]
- Lecture 18: slides [PDF]
- Lecture 19: slides [PDF]
- Lecture 20: slides [PDF]
- Lecture 21: slides [PDF]
- Lecture 22: slides [PDF]
- Lecture 23: slides [PDF]
- Lecture 24: slides [PDF] + notes on original proof of AC°≠NC¹ [PDF] (see also original paper)
- Lecture 25: slides [PDF]
A single PDF with lecture slides
Links
|
|
|
|
|
|
|
|
Contact
Teaching
