Unit 8: Randomized Complexity

This is an archived version of this module from Summer 2025.
Click here for the current iteration.

This unit covers

• probabilistic complexity classes
• pseudo-random generators
• derandomization

Material

• slides

• lecture notes

• Video 8-1 (2025-06-18, 21:47): Probabilistic complexity classes: ZPP, BPP, PP
  
• Video 8-2 (2025-06-24, 5:58): Probabilistic complexity classes: RP, co-RP
  
• Video 8-3 (2025-06-24, 11:54): Pseudorandom generators
  
• Video 8-4 (2025-06-24, 29:42): Boolean circuits
  
• Video 8-5 (2025-06-24, 16:31): Derandomization
  
• Video 8-6 (2025-06-24, 17:18): Nisan-Wigderson: Combinatorial designs
  
• Video 8-7 (2025-06-25, 51:07): Nisan-Wigderson construction
  
• Video 8-8 (2025-06-25, 3:36): Summary
  

Further reading and sources

The exposition mostly follows

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

---

Unit 7  ⋅  Syllabus  ⋅  Unit 9