Wigderson Named Turing Awardee for Decisive Work on Randomness

As a youngster in Haifa, Israel, when Avi Wigderson was getting ready to head to university, he thought that he would study math. His parents, though, argued that computer science, then a young field, might be more practical. “They said, maybe you will have an easier time finding a job after you graduate,” Wigderson recalls. “And anyway, there’ll be lots of math there.”

That decision put him on the path to being named the 2023 ACM A.M. Turing Award laureate for his foundational contributions to the theory of computation, in particular by expanding understanding of the role that randomness plays in computation and mathematics.

Wigderson, now the Herbert H. Maass Professor at the School of Mathematics at the Institute for Advanced Study in Princeton, NJ, has made a career of studying complexity theory. He also advanced our understanding of zero-knowledge proofs, which allow someone to show they know some information while keeping that information secret.

Scientists used to believe that making random choices carried an advantage when figuring out some complex problems. For example, a deterministic algorithm that looked for a large prime number, divisible only by itself and 1, would take a very long time. On the other hand, randomly picking a large integer and testing it for primality could provide an answer much quicker, as long as scientists were willing to accept a small amount of uncertainty.

Wigderson, though, showed that under natural, widely believed assumptions, any such fast probabilistic algorithm could be replaced with a fast deterministic algorithm. “Of course, the deterministic algorithm will be slower than the probabilistic one, but only moderately slower,” he says.

This is the second award Wigderson has received that has been described as the Nobel Prize of its field. In 2021 he shared the Abel Prize, which recognizes achievements in mathematics, with László Lovász of Eötvös Loránd University in Budapest, in part for bringing the two fields together.

[See a Q&A with Wigderson, “Specifying the Power and Limitations of Randomness”]

Neil Savage is a science and technology writer based in Lowell, MA, USA.

(Opening photo of Wigderson is by Alex Berg.)