Mathematician and theoretical computer scientist Avi Wigderson GS ’83 was awarded the 2021 Abel Prize, a prestigious honor awarded by the Norwegian Academy of Science and Letters that is widely considered to be the equivalent of a Nobel Prize in the field of mathematics.
Announced on March 17, the prize was awarded jointly to Wigderson and Hungarian mathematician László Lovász “for their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics.” The two will split the prize of 7.5 million Norwegian kroner, or approximately $880,000.
Wigderson is the Herbert H. Maass Professor in the School of Mathematics at the Institute for Advanced Study (IAS), where he is also the director of the program in Theoretical Computer Science and Discrete Mathematics (CSDM). Lovász is a mathematician at the Alfréd Rényi Institute of Mathematics and Eötvös Loránd University in Budapest, Hungary; he has held visiting academic positions at Princeton in the past.
Born in Haifa, Israel, in 1956, Wigderson graduated with a B.Sc. in computer science from Technion, the Israeli Institute of Technology, in 1980. He then moved to Princeton to pursue graduate studies and received a Ph.D. in electrical engineering and computer science in 1983 after completing a doctoral dissertation, titled “Studies in Computational Complexity,” under the supervision of Professor of Computer Science Emeritus Richard J. Lipton.
“When he was my student, it was immediately obvious that he was one of the smartest people that you can imagine,” Lipton told The Daily Princetonian.
Before joining the IAS faculty in 1999, Wigderson was a faculty member at the Department of Computer Science at the Hebrew University of Jerusalem, a position that he retained from 1986 to 2003. He has also held visiting positions at a number of other institutions, including the University of California, Berkeley, IBM Research, and Princeton.
One significance of the 2021 prize is that the Norwegian Academy of Science and Letters decided to award the prize, which has historically been presented to mathematicians working within pure mathematics, for work that has been done within theoretical computer science, thereby recognizing the intersection of the two fields.
“There have been questions that have always looked like they are fundamentally mathematical questions, but they really only got resolved or saw progress when they were connected to complexity theory or theoretical computer science,” Lipton explained.
Professor of Computer Science Ran Raz, who completed his Ph.D. studies under the mentorship of Wigderson at the Hebrew University of Jerusalem, commented on the magnitude of Wigderson’s impact on his field of research.
“I would say that, essentially, all mid-career and early-career researchers in complexity theory and even more generally, in theoretical computer science, were influenced by him,” Raz stated. “If you think about complexity theory, there are many different subareas, and he has key results in all of them.”
Wigderson’s research achievements mainly concern his contributions to the theory of computational complexity, which studies computational problems and tries to determine how difficult they are for algorithms to resolve.
Some of Wigderson’s most recognized contributions involve the study of randomness in computational problems. Many difficult problems can be solved more quickly if they are approached with algorithms that rely on computers to effectively flip coins in the process.
However, the downside to this method is that an algorithm reliant on randomness can be prone to error. Along with his collaborators, including Noam Nisan and Russell Impugliazzo, Wigderson showed that, given the right conditions, any algorithm reliant on randomness in this manner can be converted into a deterministic algorithm, one that does not rely on randomness, while still being able to solve the same problem quickly.
“Thanks to the leadership of Lovász and Wigderson,” the prize citation concluded, “discrete mathematics and the relatively young field of theoretical computer science are now established as central areas of modern mathematics.”
Wigderson continues the historical legacy of mathematicians and computer scientists at the University and the IAS in defining the field of computer science and shaping the technologies that stemmed from their research.
This line of individuals extends from Alan Turing GS ’38, former University professor John von Neumann, and IAS faculty member Kurt Gödel, all of whom were considered to be among the most accomplished mathematicians of the 20th century.
Wigderson is widely known as a figure who has deeply shaped the trajectory of the field of computational complexity, not only through his own research, but also through his interactions with others in the field, including over a hundred postdoctoral researchers and graduate students whom he has mentored.
One of those postdoctoral researchers is mathematics professor Maria Chudnovsky, a specialist in graph theory and combinatorics who conducted research as a member of CSDM from 2003 to 2005.
“[CSDM] is a huge group which has a couple of senior people and a large group of [postdoctoral researchers]. It doesn’t mean that everybody works on the same paper; it just means that he brings together all these people with different kinds of expertise,” Chudnovsky elaborated. “It’s a very dynamic atmosphere.”
Scott Aaronson, Professor of Computer Science and the Director of the Quantum Information Center at the University of Texas at Austin, is a former postdoctoral researcher who worked with Wigderson at the IAS.
As another well-known specialist in theoretical computer science, Aaronson described Wigderson’s importance to his field of research.
“He’s one of the most central people of our field. You can tell him anything, and he’ll see everything else that’s connected to it,” Aaronson said. “I would think of him as a central node. There’s pretty much no part of the [complexity theory] field that Avi hasn’t worked on.”
2021 marks the fourth consecutive year in which the Abel Prize was awarded to a mathematician who is affiliated with the University. Wigderson is the ninth recipient of the prize affiliated with the University since it was first awarded in 2003.
The award ceremony will take place at a future date when His Majesty King Harald V of Norway is able to safely present the prize to the 2021 laureates.
Wigderson declined to be interviewed for this article.