Derandomization

Description:
Randomized algorithms can solve problems that seem to require much more work deterministically. A single coin flip can replace a complicated search. But is any of that power real, or is every randomized algorithm just a deterministic one we haven't been clever enough to find? This video walks through the core techniques of derandomization: enumeration, Adleman's theorem that BPP is in P/poly, the method of conditional expectations applied to MaxCut, pairwise independence, pseudorandom generators, and the Nisan-Wigderson construction. Everything converges on the Impagliazzo-Wigderson theorem: if E contains a function requiring exponential circuits, then BPP equals P. The hardness we want to prove would give us the pseudorandomness that blocks the proof techniques we know. Whether randomness is necessary for efficient computation and whether computation has structure we can prove turn out to be the same question.

Companion article: https://computablesecrets.com/videos/5tniH32qW44.

If you want to support this work, please sign up for the membership on my website: https://computablesecrets.com.

Credits:
- "Hardness vs Randomness" by N. Nisan and A. Wigderson (1994)
- "P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma" by R. Impagliazzo and A. Wigderson (1997)
- "Pseudorandomness" by S. Vadhan (2012)
- "Hardness as Randomness: A Survey of Universal Derandomization" by R. Impagliazzo (2003)
- Manim (Python library for visuals)
- Claude Code (assistance in editing and production)