ACM announced that the 2023 ACM AM Turing Award will be awarded to Avi Wigderson for his contributions to the field of theoretical computer science, particularly transforming our understanding of how randomness operates in computation.
“Wigderson is a towering intellectual force in theoretical computer science, an exciting discipline that attracts the most promising young researchers and drives them to solve our most difficult challenges,” said Yannis Ioannidis, president of ACM. “This year’s Turing Award recognizes not only Wigderson’s specific work on randomness, but also the indirect but substantial impact he has had on the entire field of theoretical computer science.”
Basically, computers are deterministic systems. In other words, a computer’s algorithms follow predictable patterns in which the output is determined by the input. But because the world we live in is full of random events, computer scientists have made algorithms more efficient by allowing them to also make random choices. There are many use cases for which no deterministic algorithm is possible, so these probabilistic algorithms are used instead.
According to the ACM, many computer scientists have focused their research on uncovering the relationship between randomness and pseudorandomness in computation.
“Is randomness essential or can it be eliminated? And what quality of randomness is necessary for the success of a probabilistic algorithm? These and many other fundamental questions are central to understanding randomness and pseudo-randomness in computation. “A better understanding of the dynamics of randomness in computation can not only lead to the development of better algorithms, but also deepen our understanding of the nature of computation itself,” the ACM said. post Announcing this year’s winners.
Wigderson’s research demonstrated that “all stochastic polynomial-time algorithms can be efficiently derandomized” and that randomness is not essential for efficient computing.
The three papers he wrote on this topic have since been used by other computer scientists and led to several other new ideas.
His work studying randomness is computational, and his other interests include multi-proof interactive proofs, cryptography, and circuit complexity.
ACM also highlighted the fact that Wigderson has mentored many young researchers in the field. He currently serves as Professor 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 for theoretical computer science for the past 30 years,” said Jeff Dean, senior vice president at Google. “Since the early days of computer science, researchers have recognized that incorporating randomness is a way to design faster algorithms for a wide range of applications. Efforts to better understand randomness continue to provide important benefits to our field, and Wigderson is breaking new ground in the field. Google also honors Wigderson’s role as a mentor. His colleagues credit him with providing great ideas and research directions and motivating a new generation of bright, young researchers to engage in that research. Congratulations to Avi Wigderson on receiving the ACM AM Turing Award, computing’s highest honor.”