Computer scientist wins Turing Award for seminal work on randomness

Computational scientist and mathematician Avi Wigderson of the Institute for Advanced Study (IAS) at Princeton University has won the 2023 A.M. Turing Award. The prize, which is given annually by the Association for Computing Machinery (ACM) to a computer scientist for their contributions to the field, comes with $1 million thanks to Google. It is named in honor of the British mathematician Alan Turing, who helped develop a theoretical foundation for understanding machine computation.

Wigderson is being honored “for foundational contributions to the theory of computation, including reshaping our understanding of the role of randomness in computation and for his decades of intellectual leadership in theoretical computer science.” He also won the prestigious Abel Prize (essentially the Nobel for mathematics) in 2021 for his work in theoretical computer science—the first person to be so doubly honored.

“Avi has made fundamental contributions to the theory of computation from parallel algorithms to cryptography to absolutely all aspects of complexity theory,” said Shafi Goldwasser, director of the Simons Institute for the Theory of Computing, who won the 2012 Turing Award. “His numerous contributions over decades to the areas of derandomization and pseudorandomness has led us to a deep understanding of the deep role of randomness in computing.”

Born in Haifa, Israel, Wigderson was the son of an electrical engineer and a nurse. His father passed his own love of solving puzzles and mathematics to his son. Wigderson was an undergraduate at the Technion (Israeli Institute of Technology) and went on to earn his PhD in computer science from Princeton in 1983. He held a few short-term positions before joining the faculty of Hebrew University three years later. He has been with the IAS since 1999 and a full-time resident since 2003.

While computers are fundamentally deterministic systems, researchers discovered in the 1970s that they could enrich their algorithms by letting them make random choices during computation in hopes of improving their efficiency. And it worked. It was easier for computer scientists to start with a randomized version of a deterministic algorithm and then “de-randomize” it to get an algorithm that was deterministic.

In 1994, Wigderson co-authored a seminal paper on hardness versus randomness with Noam Nisan, demonstrating that as useful as randomness can be, it is not a necessity. Essentially, “Every probabilistic algorithm that’s efficient can be replaced by a deterministic one, so you don’t really need [randomness],” he said. “The power believed to be in probabilistic algorithms doesn’t exist.” He subsequently coauthored two more highly influential papers further extending that work on randomness, among many others.

Wigderson’s 2019 book, Mathematics and Computation: A Theory Revolutionizing Technology and Science, is available for download on his website. “One central theme is that computation happens everywhere, not just in computers,” Wigderson told Ars. “It is part of the processes in our brain, the way we can talk and the cells in our body, but also trees growing or weather and celestial things. In all these natural processes, there are the laws of nature, which are local, and they evolve systems. Like in a computer, there are very simple rules, and you start with a problem and discover a complex solution to it. So, the methodology is applicable to essentially any science process or study. There are fantastic collaborations with statistical physics, with quantum physics, with computational biology, with economics, with social science—lots of beautiful, extremely fruitful connections.”

Wigderson’s own research is purely theoretical. “I’m not motivated by applications,” he said. “But I know that fundamental work, we find uses. Think about Alan Turing. He wrote a mathematical paper in logic in an obscure journal about Entscheidungsproblem. It was not motivated by application. But this is what starts computer science. He himself recognized the model he was suggesting is so simple, that we can just start building it.”

That said, he does confess to being pleasantly surprised by the eventual application of his work on zero-knowledge interactive proofs in the mid-1980s. With Silvio Micali and Oded Goldreich, Wigderson extended Micali’s earlier work on interactive proofs to NP problems, concluding that the solution to every such problem can also be proved with a zero-knowledge proof.

“Basically we discovered that everything that can be proved, can be proved, without revealing to the person who is verifying the proof any knowledge they didn’t know,” said Wigderson. “The motivation came from cryptography, where I want to prove to you that I selected my secret key in the way the protocol requires, but I don’t want to tell you what my secret key is. The result is very general and while very satisfying, it was a theoretical solution that it seemed to me very complicated to implement. But now variants of it are part of blockchains and other crypto systems. So sometimes we are surprised by the diligence of people who really care about practice and really want to see things working.”

Wigderson remains as actively curious as ever and is particularly excited about getting to collaborate with fresh groups of postdocs every year. One current project concerns convex optimization in non-Euclidean settings. Convex optimization has been broadly applied in machine learning, signal processing, computer vision, and automatic control systems, for example. Wigderson’s project seeks to “generalize the theory to manifolds, to structures that appear in quite a variety of mathematical and physics areas—quantum information theory, invariant theory, and definitely in computer science,” he said. “It also appears in analysis, for proving inequalities, and in algebra for proving identities. It’s pretty broad, and I’m very excited about it.”