Mathematician wins Turing award for harnessing randomness

Avi Wigderson has won the 2023 Turing award for his work on understanding how randomness can shape and improve computer algorithms

By Alex Wilkins

10 April 2024

Avi Wigderson, winner of the 2023 Turing award

Peter Badge

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.”

Read more

Is everything predetermined? Why physicists are reviving a taboo idea

Advertisement

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.