Support us on Patreon:   / 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 Zeroknowledge proofs

Blog post: coming soon
Code for the animations: https://github.com/polylogcs/derando...

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:    • Interview with Avi Wigderson, 2021 Ab...   and    • Professor Avi Wigderson on a computat...  
Seismograph:    • Tremors (2/10) Movie CLIP  Old Fred'...