Рет қаралды 88,224
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 Zero-knowledge proofs
Blog post: coming soon
Code for the animations: github.com/polylog-cs/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 docs.manim.community/en/stable/
Color palette: Solarized ethanschoonover.com/solarized/
Music: Thannoid by Blue Dot Sessions
Pictures: Wikipedia, Internet
Video clips used:
Avi Wigderson: • Interview with Avi Wig... and • Professor Avi Wigderso...
Seismograph: • Tremors (2/10) Movie C...