Mathematician and theoretical computer scientist Avi Wigderson has received the prestigious 2023 Turing Award for his groundbreaking contributions to the understanding of “randomness” in computation.
The Association for Computing Machinery’s (ACM) Turing Award recognises those who have made a significant contributions to computing and is widely lauded as the field’s equivalent to a Nobel Prize.
Handed out annually, winners from prior years include Tim Berners-Lee, the inventor of the World Wide Web, and Geoffrey Hinton, the ‘Godfather of AI’ whose work contributed greatly to the understanding of artificial neural networks.
Wigderson, who earned his PHD in computer science in 1983, yesterday joined some of computer science’s most esteemed figures when he was handed the award for his “foundational contributions” to computing, including “reshaping our understanding” of the role of randomness in computation.
A computational scientist and mathematician at the Institute for Advanced Study (IAS) in Princeton, New Jersey, Wigderson authored a “highly influential” series of works on trading hardness for randomness.
Wigderson’s work upended assumptions about the need for computers to add random or pseudorandom choices when running probabilistic algorithms.
In the words of ACM, Wigderson and his colleagues “proved that, under standard and widely believed computational assumptions, every probabilistic polynomial time algorithm can be efficiently derandomized”.
In 1994, Wigderson and Noam Nisan authored a seminal paper arguing that “efficient deterministic simulation of randomised algorithms is possible under much weaker assumptions than previously known”.
“Our results are very strong evidence that the gap between randomised and deterministic complexity is not large,” the paper read.
ACM described Wigderson’s works as having “revolutionised” the understanding of randomness in computation, and further notes his ideas were subsequently adopted in many areas of theoretical computer science, enabling “impactful papers” by several leading figures in the field.
“Natural processes can be viewed as computers,” said Wigderson. “Computational processes are everywhere.”
Wigderson explained theoretical computer science has significant overlap with other branches of science, including physics, biology, economics and even social sciences – observing computational processes hold relevance in non-computational areas, from “bacteria in petri dishes” through to “gossip on the internet”.
“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 said.
The organisation praised Wigderson for his “decades of intellectual leadership” in theoretical computer science, making particular note of his ongoing mentorship at the IAS School of Mathematics in Princeton, New Jersey – where Wigderson has been a leading professor since 1999.
“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,” ACM president Yannis Ioannidis said.
Wigderson also won the mathematics-focused Abel Prize in 2021, marking the first person to be receive both prestigious awards, as well as the Nevanlinna Prize in 1994 for his work on computational complexity.
The Turing Award – which was named in honour of British mathematician and computational forefather Alan Turing – comes with $USD 1 million thanks to Google.
Jeff Dean, senior vice president at Google. said Wigderson’s work on randomness and other topics has “set the agenda in theoretical computer science for the past three decades”.
“We congratulate Avi Wigderson on receiving the ACM A.M. Turing Award – computing’s highest honour,” Dean said.
