Avi Wigderson

Digital Library

ACM A. M. Turing Award

USA - 2023



For foundational contributions to the theory of computation, including reshaping our understanding of the role of randomness in computation and mathematics, and for his decades of intellectual leadership in theoretical computer science

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.

In a related but distinct sequence of results, Wigderson and colleagues gave the first efficient combinatorial (as opposed to algebraic) constructions of expander graphs or networks. Expander graphs are carefully designed networks with few edges but strong connectivity properties, and they have many important applications in both computer science and mathematics, including pseudorandom number generation and error-correcting codes. For many purposes, the combinatorial constructions of Wigderson are far more convenient and inspired several breakthroughs in computational complexity theory. Wigderson's research on expanders has led to a rich and important vein of interdisciplinary follow-up work in computer science, combinatorics, and related fields.

Wigderson has also made far-reaching contributions to the theory of computational complexity and cryptography. These include his participation in the introduction of multi-prover interactive proofs, which generalize both traditional mathematical proofs as well as single-prover interactive proofs. They allow a verifier, wishing to check the correctness of a statement, to interact with multiple provers. Wigderson's results in this model demonstrated that it is possible have zero-knowledge proofs without computational assumptions, in contrast to the single prover model such assumptions are necessary. This work also led to many further milestone achievements, including probabilistically checkable proofs and fundamental results on the hardness of approximating intractable optimization problems.

Wigderson's Turing nomination also emphasized that he has been a beloved leader and mentor in the theoretical computer science community for decades, and has deeply influenced generations of researchers. He is known for his openness, curiosity, kindness and warmth in his approach to both research and colleagues.

Press Release

ACM Fellows

USA - 2018


For contributions to theoretical computer science and mathematics

Press Release