ACM has announced that it is awarding the 2023 ACM A.M. Turing Award to Avi Wigderson for his contributions in the area of theoretical computer science, and notably, for changing our understanding of how randomness works in computation.
“Wigderson is a towering intellectual force in theoretical computer science, an exciting discipline that attracts some of the most promising young researchers to work on the most difficult challenges,” said Yannis Ioannidis, president of ACM. “This year’s Turing Award recognizes Wigderson’s specific work on randomness, as well as the indirect but substantial impact he has had on the entire field of theoretical computer science.”
At their core, computers are deterministic systems, meaning their algorithms follow a predictable pattern where output is determined by the input. But the world we live in is full of random events, so computer scientists have enabled algorithms to make random choices too, which makes them more efficient. There are also many use cases where there isn’t a possible deterministic algorithm, so these probabilistic algorithms have been used instead.
Many computer scientists have devoted their research to uncovering the relationship between randomness and pseudorandomness in computation, according to ACM.
“Is randomness essential, or can it be removed? And what is the quality of randomness needed for the success of probabilistic algorithms? These, and many other fundamental questions lie at the heart of understanding randomness and pseudorandomness in computation. An improved understanding of the dynamics of randomness in computation can lead us to develop better algorithms as well as deepen our understanding of the nature of computation itself,” ACM wrote in the post announcing this year’s award winner.
Wigderson’s research proved that “every probabilistic polynomial time algorithm can be efficiently derandomized” and that randomness isn’t essential for efficient computing.
Three of the papers he authored on this topic were then used by other computer scientists and led to several other new ideas.
Besides his work studying randomness is computation, his other areas of interest have included multi-prover interactive proofs, cryptography, and circuit complexity.
ACM also highlighted the fact that Wigderson has mentored many young researchers in the field. He is currently a professor in the School of Mathematics at the Institute for Advanced Study in Princeton, New Jersey.
“Avi Wigderson’s work on randomness and other topics has set the agenda in theoretical computer science for the past three decades,” said Jeff Dean, senior vice president of Google. “From the earliest days of computer science, researchers have recognized that incorporating randomness was a way to design faster algorithms for a wide range of applications. Efforts to better understand randomness continue to yield important benefits to our field, and Wigderson has opened new horizons in this area. Google also salutes Wigderson’s role as a mentor. His colleagues credit him with generating great ideas and research directions, and then motivating a new generation of smart young researchers to work on them. We congratulate Avi Wigderson on receiving the ACM A.M. Turing Award—computing’s highest honor.”