We would like to congratulate the 2023 ACM A.M. Turing Award recipient Avi Wigderson, who has been recognized by the Association for Computing Machinery “for foundational contributions to the theory of computation, including reshaping our understanding of the role of randomness in computation, and for his decades of intellectual leadership in theoretical computer science.”

The ACM A.M. Turing Award is often referred to as the “Nobel Prize of Computing.” It carries a $1 million prize and is named for Alan Mathison Turing, the British mathematician who articulated the mathematical foundations of computing.

A leader in theoretical computer science research for four decades, Wigderson has made foundational contributions to the understanding of the role of randomness and pseudorandomness in computation.

Computer scientists have discovered a remarkable connection between randomness and computational difficulty (i.e., identifying natural problems that have no efficient algorithms). Working with colleagues, Wigderson authored a highly influential series of works on trading hardness for randomness. They proved that, under standard and widely believed computational assumptions, every probabilistic polynomial time algorithm can be efficiently derandomized (namely, made fully deterministic). In other words, randomness is not necessary for efficient computation. This sequence of works revolutionized our understanding of the role of randomness in computation, and the way we think about randomness. This series of influential papers includes “Hardness vs. Randomness,”“BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs” and “P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma.”

Outside of his work in randomness, Wigderson has been an intellectual leader in several other areas of theoretical computer science, including multi-prover interactive proofs, cryptography, and circuit complexity.

more

Category: HLFF Forum