By Scott Lyon
Princeton graduate alumnus Avi Wigderson has won the 2023 A.M. Turing Award from the Association for Computing Machinery (ACM), recognizing his profound contributions to the mathematical underpinnings of computation.
The Turing Award is considered the highest honor in computer science, often called the “Nobel Prize of Computing.”
Wigderson, the Herbert H. Maass Professor in the Institute for Advanced Study’s School of Mathematics, earned his Ph.D. from Princeton in 1983 in what was then the Department of Electrical Engineering and Computer Science.
In addition to the Turing Award, he is also the recipient of the 2021 Abel Prize, considered the highest honor in mathematics, from the Norwegian Academy of Science and Letters. He is the only person ever to have won both the Abel Prize and the Turing Award.
“Mathematics is foundational to computer science and Wigderson’s work has connected a wide range of mathematical sub-areas to theoretical computer science,” ACM President Yannis Ioannidis said in a statement released by the organization.
“Avi Widgerson is a giant in the field of theoretical computer science, bringing fundamental insights to deep questions about what can — or cannot — be computed efficiently,” said Jennifer Rexford, Princeton’s provost and Gordon Y.S. Wu Professor of Engineering. “He is also a wonderful colleague and a long-time friend of the University.”
Wigderson is best known for his work on computational complexity theory, especially the role of randomness in computation. Namely, in a series of highly influential works from the 1990s, Wigderson and colleagues proved that computation can be efficient without randomness, shaping algorithm design ever since. He has also established important ideas in several other areas, including protocol design and cryptography, which enables much of today’s digital infrastructure.
While his work is primarily mathematical, the notions he is trying to understand through that work are computational, Wigderson said in a video released by the Institute for Advanced Study (IAS). That approach has earned him a reputation as one of the most versatile minds in either discipline.
“He is one of the most central people in theoretical computer science, generally,” said Ran Raz, a professor of computer science at Princeton, who was Wigderson’s graduate student at the Hebrew University in Jerusalem.
Wigderson has influenced countless students and thinkers, having mentored more than 100 postdocs and collaborated with an unusually broad range of scholars. “He is always able to make connections between things,” Raz said.
“He’s an inspiration,” said Pravesh Kothari, an assistant professor of computer science at Princeton and a former postdoctoral advisee of Wigderson’s at IAS. “He’s a role model. If I could become 10 percent of the researcher he is, it would be a fantastic success for my career.” Kothari also said Wigderson implores young researchers to view the entire endeavor as one field. And that approach shows up in all of his work, connecting disparate problems from sub-disciplines that are normally seen as unrelated.
His research has “set the agenda in theoretical computer science” for decades, Google Senior Vice President Jeff Dean said in the ACM press release. His work has also found its way directly into everyday life.
In a series of findings at the intersection of mathematics and computer science, Wigderson cemented what is known as the zero-knowledge proof, critical in cryptography and digital security. The technique has found purchase in modern applications of privacy, compliance, identity verification and blockchain technology.
Raz said he was amazed at how far Wigderson’s ideas had traveled, from the depths of mathematics to the technologies that enable global enterprise to the everyday lives of billions of people. “It’s quite amazing that these things can be made practical,” Raz said.
Szymon Rusinkiewicz, the David M. Siegel ’83 Professor of Computer Science and department chair, added that Wigderson has been a great friend to Princeton’s computer science community, including to students and young scholars. “He has had a great influence throughout the world of computer science, and we especially feel that at Princeton, where he has been a great mentor and collaborator.”
Wigderson is the recipient of numerous other awards, including the 1994 IMU Abacus Medal, the 2009 Gödel Prize and the 2019 Donald E. Knuth Prize. He is currently a Fellow of the ACM, a member of the American Academy of Arts and Sciences and a member of the National Academy of Sciences.
At Princeton, in addition to his Ph.D., he earned an M.S.E. in 1981, an M.A. in 1982, and he later served on Princeton’s computer science faculty from 1990 to 1992. He joined IAS in 1999, where he established the program in Computer Science and Discrete Mathematics.