#wigderson — Public Fediverse posts
Live and recent posts from across the Fediverse tagged #wigderson, aggregated by home.social.
-
#Avi #Wigderson is the recipient of the 2023 ACM A.M. #Turing #Award.
Wigderson's groundbreaking contributions to theoretical computer science include results that have🔸 elucidated both the power and limitations of #randomness in #computation. 🔸
Wigderson is the Herbert H. Maass Professor in the School of Mathematics at the Institute for Advanced Study in Princeton, New Jersey.
Prior to Wigderson's contributions, it appeared quite plausible that randomized algorithms might be qualitatively faster than deterministic computation for many fundamental problems. For example, efficient algorithms for finding large primes - a computation essential to modern cryptography - use randomization.
In a landmark series of works, Wigderson and colleagues proved that,
under standard and widely believed computational assumptions, ⭐️every efficient randomized algorithm can in fact be fully derandomized. ⭐️
In other words, randomness is not necessary for efficient computation.
These results revolutionized our understanding of the role of randomness in algorithms, and the way we think about randomness more generally in mathematics and computer science.