By Donald Gilpin

Avi Wigderson
(Photo by Cliff Moore, IAS)

Avi Wigderson, the Herbert H. Maass Professor in the Institute for Advanced Study (IAS) School of Mathematics, has been awarded the 2023 Association for Computing Machinery’s (ACM) A.M. Turing Award for his groundbreaking work in theoretical computer science and the role of randomness in computation.

The Turing Award, often referred to as the “Nobel Prize of Computing,” comes with a prize of $1 million. Wigderson, who won the 2021 Abel Prize, considered the highest honor in mathematics, is the only person ever to have won both Turing and Abel awards.

In announcing the award, the ACM noted Wigderson’s “reshaping our understanding of the role of randomness in computation” and “his decades of intellectual leadership in theoretical computer science.”

The ACM also cited his leadership in the areas of “computational complexity theory, algorithms and optimization, randomness and cryptography, parallel and distributed computation, combinatorics, and graph theory, as well as connections between theoretical computer science and mathematics and science.”

In a conversation with IAS Director David Nirenberg, Wigderson discussed his Turing Award and his career in the mathematics of computer science. Wigderson leads the program in Computer Science and Discrete Mathematics, which was formally established at IAS in 1999 when he was appointed to the permanent faculty there.

“That’s the field I chose, and that’s where I stayed these four decades, and I’m extremely happy that I had such luck choosing this area,” he said. “I wouldn’t change anything. I think that it is blessed with all the virtues that one can hope for in a research area. It contains an amazing collection of deep and intellectually fundamental questions that are important to people, to science, to life, to technology.”

He continued, “There is an amazing set of brilliant people who are in this field, and they’re not just brilliant, they’re exceedingly nice. Somehow the atmosphere in this field is fantastic. And many of my lifelong friends have been students of mine or collaborators of mine. It’s hard to imagine that I could find anything better anywhere.”

Wigderson, as quoted in an IAS press release, described his four decades in the field as “a continuous joyride, with fun problems, brilliant researchers.”

Google Senior Vice President Jeff Dean, as quoted in an ACM press release, claimed that Wigderson’s work had “set the agenda in theoretical computer science for the past three decades.”

Dean pointed out, “From the earliest days of computer science, researchers have recognized that incorporating randomness was a way to design faster algorithms for a wide range of applications. Efforts to better understand randomness continue to yield important benefits to our field, and Wigderson has opened new horizons in this area.”

He went on, “Google also salutes Wigderson’s role as a mentor. His colleagues credit him with generating great ideas and research directions, and then motivating a new generation of smart young researchers to work on them.”

The IAS press release pointed out that Wigderson is part of a long tradition of computational research at the Institute. Founding IAS faculty member John von Neumann’s Electronic Computer Project, launched in 1945, resulted in the construction at IAS of one of the world’s first stored-program computers. That computer represented the practical manifestation of the foundations of computing set forth by British mathematician Alan M. Turing, who gives his name to the Turing Award.

“Ever since von Neumann’s IAS computer project turned Turing’s theoretical computational model into a reality that launched the computing revolution, theorists following their curiosity and mathematical insights have paved the way for the new computing technologies we all use,” said Nirenberg. “Avi has continued that tradition at the Institute for the past quarter century.”

Wigderson, 67, earned his Ph.D. from Princeton University in 1983 in what was then the Department of Electrical Engineering and Computer Science. Prior to joining the IAS faculty he held academic appointments at a number of universities, including the Hebrew University of Jerusalem (1986-2003) and Princeton (1990-92).

Jennifer Rexford, Princeton provost and engineering professor, as quoted in a University press release, described Wigderson as “a giant in the field of theoretical computer science, bringing fundamental insights to deep questions about what can — or cannot — be computed efficiently.” She added, “He is also a wonderful colleague and a longtime friend of the University.”