Giải thưởng Turing năm nay thuộc về...

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