Avi Wigderson wins $1 million Turing Award for using randomness to change computer science

Avi Wigderson is the winner of the 2023 Turning Award for his studies in randomness.
Avi Wigderson is the winner of the 2023 Turning Award for his studies in randomness. (Image credit: Peter Badge)

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.

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.

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
Staff Writer

Ben Turner is a U.K. based staff writer at Live Science. He covers physics and astronomy, among other topics like 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.