Unit 8: Randomized Complexity

This unit covers

• probabilistic complexity classes
• pseudo-random generators
• derandomization

Material

• slides

• lecture notes

• Video 8-1 (2025-06-18): Probabilistic complexity classes: ZPP, BPP, PP

• Video 8-2 (2025-06-24): Probabilistic complexity classes: RP, co-RP

• Video 8-3 (2025-06-24): Pseudorandom generators

• Video 8-4 (2025-06-24): Boolean circuits

• Video 8-5 (2025-06-24): Derandomization

• Video 8-6 (2025-06-24): Nisan-Wigderson: Combinatorial designs

• Video 8-7 (2025-06-25): Nisan-Wigderson construction

• Video 8-8 (2025-06-25): Summary

Further reading and sources

The exposition mostly follows

• S. Arora and B. Barak: Computational Complexity: A Modern Approach

---

Unit 7  ⋅  Syllabus  ⋅  Unit 9