Support us on Patreon: https://www.patreon.com/Polylog
We explain why Avi Wigderson got this year’s Turing award: We show how you can make any randomized algorithm deterministic.
0:00 Intro
2:41 P = BPP
5:38 Statistical tests
7:52 Pi as a PRNG
9:44 Nisan–Wigderson PRNG
13:47 Finishing the proof
14:45 Zero-knowledge proofs
Blog post: coming soon
Code for the animations: https://github.com/polylog-cs/derandomization/
Richard Hladík: Script editor, animator
Václav Rozhoň: Writer, animator
Václav Volhejn: Narrator, animator, script editor
Thank you to our beta testers: Matěj, Honza, Filip
Animations: manim, a Python library https://docs.manim.community/en/stable/
Color palette: Solarized https://ethanschoonover.com/solarized/
Music: Thannoid by Blue Dot Sessions
Pictures: Wikipedia, Internet
Video clips used:
Avi Wigderson: https://www.youtube.com/watch?v=YOrBVEwDqAg and https://www.youtube.com/watch?v=ZzsFb-6wvoE
Seismograph: https://www.youtube.com/watch?v=mbKEarx9CCs