And this year's Turing Award goes to...

Abstract

An exposition of the work that earned Avi Wigderson the 2023 ACM A.M. Turing Award, in particular the “hardness vs. randomness” framework he developed with Nisan and others. The video shows how, if natural hard problems exist, every efficient randomized algorithm can in principle be replaced by an efficient deterministic one, reshaping our understanding of the role of randomness in computation.