The ACM announced that it is awarding the 2023 ACM AM Turing Award to Avi Wigderson for his contributions to the field of theoretical computer science, and in particular for changing our understanding of how randomness works in computation.
“Wigderson is a major intellectual force in theoretical computer science, an exciting discipline that attracts some of the most promising young researchers to work on the toughest challenges,” said Yannis Ioannidis, ACM president. “This year’s Turing Award recognizes Wigderson’s specific work on randomness, as well as the indirect but significant impact he has had on the entire field of theoretical computer science.”
At their core, computers are deterministic systems, meaning that their algorithms follow a predictable pattern where the 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 as well, which makes them more efficient. There are also many use cases where no deterministic algorithm is possible, so these probabilistic algorithms are used instead.
Many computer scientists have devoted their research to uncovering the relationship between randomness and pseudorandomness in computing, according to the ACM.
“Does randomness matter or can it be removed? And what quality of randomness is required for the success of probabilistic algorithms? These and many other fundamental questions lie at the heart of understanding randomness and pseudorandomness in computing. 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,” wrote the ACM in publish announcement of this year’s award winner.
Wigderson’s research proved that “any probabilistic polynomial time algorithm can be efficiently derandomized” and that randomness is not necessary for efficient computation.
The three papers he wrote on this topic were then used by other computer scientists and led to several new ideas.
In addition to studying randomness in computing, his other areas of interest included interactive proofs with multiple provers, cryptography, and circuit complexity.
ACM also highlighted the fact that Wigderson 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 at Google. “Since the earliest days of computer science, researchers have recognized that incorporating randomness is a way to design faster algorithms for a wide variety of applications. Efforts to better understand randomness continue to bring important benefits to our field, and Wigderson has opened new horizons in this field. Google also welcomes Wigderson’s role as a mentor. His colleagues are credited with generating great ideas and research directions and then motivating a new generation of bright young researchers to work on them. Congratulations to Ava Wigderson on receiving the ACM AM Turing Award—computing’s highest honor.”