Mathematician wins Turing award for harnessing randomness

The mathematician Avi Wigderson has won the 2023 Turing award, often referred to as the Nobel prize for computing, for his work on understanding how randomness can shape and improve computer algorithms.

Wigderson, who also won the prestigious Abel prize in 2021 for his mathematical contributions to computer science, was taken aback by the award. “The [Turing] committee fooled me into believing that we were going to have some conversation about collaborating,” he says. “When I zoomed in, the whole committee was there and they told me. I was excited, surprised and happy.”

Computers work in a predictable way at the hardware level, but this can make it difficult for them to model real-world problems, which often have elements of randomness and unpredictability. Wigderson, at the Institute for Advanced Study in Princeton, New Jersey, has shown over a decades-long career that computers can also harness randomness in the algorithms that they run.

In the 1980s, Wigderson and his colleagues discovered that by inserting randomness into some algorithms, they could make them easier and faster to solve, but it was unclear how general this technique was. “We were wondering whether this randomness is essential, or maybe you can always get rid of it somehow if you’re clever enough,” he says.

One of Wigderson’s most important discoveries was making clear the relationship between types of problems, in terms of their difficulty to solve, and randomness. He also showed that certain algorithms that contained randomness and were hard to run could be made deterministic, or non-random, and easier to run.

These findings helped computer scientists better understand one of the most famous unproven conjectures in computer science, called “P ≠ NP”, which proposes that easy and hard problems for a computer to solve are fundamentally different. Using randomness, Wigderson discovered special cases where the two classes of problem were the same.

Wigderson first started exploring the relationship between randomness and computers in the 1980s, before the internet existed, and was attracted to the ideas he worked on by intellectual curiosity, rather than how they might be used. “I’m a very impractical person,” he says. “I’m not really motivated by applications.”

However, his ideas have become important for a wide swath of modern computing applications, from cryptography to cloud computing. “Avi’s impact on the theory of computation in the last 40 years is second to none,” says Oded Goldreich at the Weizmann Institute of Science in Israel. “The diversity of the areas to which he has contributed is stunning.”

One of the unexpected ways in which Wigderson’s ideas are now widely used was his work, with Goldreich and others, on zero-knowledge proofs, which detail ways of verifying information without revealing the information itself. These methods are fundamental for cryptocurrencies and blockchains today as a way to establish trust between different users.

Although great strides in the theory of computation have been made over Wigderson’s career, he says that the field is still full of interesting and unsolved problems. “You can’t imagine how happy I am that I am where I am, in the field that I’m in,” he says. “It’s bursting with intellectual questions.”

Wigderson will receive a $1 million prize as part of the Turing award.