Live Science Plus
Avi Wigderson wins $1 million Turing Award for using randomness to change computer science
The 2023 Turing Award has been given to Avi Wigderson . The mathematician found that adding randomness into algorithms made them better at solving nondeterministic problems.
The 2023 Turing Award has been given to Avi Wigderson, a mathematician who discovered the strange connection between computation and randomness.
Wigderson was announced the winner of the Association for Computing Machinery (ACM) A.M. Turing Award, often called the "Nobel Prize of Computing," on April 10, 2024.
The award, given with a prize of $1 million, comes just three years after Wigderson, a professor of mathematics at the Institute for Advanced Study in Princeton, New Jersey, won the 2021 Abel Award for his contributions to computer science. Wigderson's theoretical work has been key to the development of numerous advances in computing, from cloud networks to cryptography methods that underpin cryptocurrencies.
"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," Yannis Ioannidis, president of the ACM, said in a statement. "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."
Related: Scientists uncover hidden math that governs genetic mutations
Computer algorithms are deterministic by nature, which enables them to make predictions but also limits their grasp of the messy randomness found in the real world. In fact, many problems are considered computationally “hard”, and deterministic algorithms struggle to solve them efficiently.
RELATED STORIES
But Wigderson and his colleague Richard Karp, a computer scientist at the University of California, Berkeley, found a way to tame computational hardness. After inserting randomness into their algorithms, they found that they made some problems much easier to solve.
Get the world’s most fascinating discoveries delivered straight to your inbox.
Wigderson chased this observation, proving in later work that the reverse also applied: Randomness could always be stripped from probabilistic algorithms to transform them into deterministic ones. His findings illuminated the connection between computational hardness and randomness in ways that reshaped computer science.
"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," Jeff Dean, chief scientist at Google Research and Google DeepMind, said in the statement. "Efforts to better understand randomness continue to yield important benefits to our field, and Wigderson has opened new horizons in this area."
Ben Turner is a U.K. based writer and editor at Live Science. He covers physics and astronomy, tech and climate change. He graduated from University College London with a degree in particle physics before training as a journalist. When he's not writing, Ben enjoys reading literature, playing the guitar and embarrassing himself with chess.