Avi Wigderson of the Institute for Advanced Study (IAS) in Princeton has been named a recipient of the 2021 Abel Prize, which he shares jointly with László Lovász – a former IAS visiting professor — of Eötvös Loránd University.
Wigderson and Lovász are cited by the Abel committee “for their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics,” according to a statement provided by IAS.
Wigderson, currently Herbert H. Maass professor in the School of Mathematics, leads the IAS program in Computer Science and Discrete Mathematics (CSDM), which was formally established at the Institute in 1999 with Wigderson’s appointment to the permanent faculty, according to the statement.
“I am thrilled that the mathematics community has recognized with this prize the entire field of the theory of computation, which has been my academic and social home for the past four decades,” Wigderson said in the statement. “I feel lucky to be part of this extremely dynamic community, whose fundamental goals have at the same time deep conceptual and intellectual meaning, scientific and practical motivations, with pure fun problems and brilliant collaborators to pursue them with.”
Wigderson is recognized for his prolific contributions to the major areas of computational complexity theory, including randomized computation, algorithms and optimization, circuit complexity, proof complexity, quantum computation, cryptography, and understanding of fundamental graph properties, according to the statement.
“Avi Wigderson stands, in the tradition of Gödel and von Neumann, at the pinnacle of the theory of computation,” Robbert Dijkgraaf, IAS Director and Leon Levy professor, said in the statement. “His work shows how some of the deepest ideas in mathematics are intimately connected to a technology that is totally transforming our society. Avi is also a convincing advocate for computation as a powerful and promising perspective on all fields of knowledge. I am honored to congratulate Avi and László as this year’s Abel laureates and applaud their ongoing leadership and mentorship of young researchers in this fast-evolving field.”
John von Neumann, one of the institute’s founding professors, pioneered the Electronic Computer Project, which resulted in the construction of the world’s first stored-program computer in the basement of Fuld Hall. His colleague Kurt Gödel, one of history’s greatest logicians, had a foundational impact on Alan Turing and the study of computability, according to the statement. While at IAS, Gödel was the first to contemplate a version of the P vs. NP problem and to understand its importance.
Wigderson has carried the torch forward into the next century, producing paradigm-shifting ideas powering the future of computing, according to the statement.
“From its inception, complexity theory produced challenging mathematical problems. As the theory matured and its problems were vigorously probed, many of them turned out to be fundamental in computational theory as well as in diverse mathematical areas,” Peter Sarnak, professor in the School of Mathematics, said in the statement. “Laci Lovász and Avi Wigderson have been at the center of many of the breakthroughs that have shaped these flourishing areas of theoretical computer science and mathematics, and especially their very fruitful marriage. The doors that they have opened, coupled with their leadership and generosity, have allowed many others to achieve lofty goals in these areas. It is wonderful to see them recognized with the Abel Prize.”
Wigderson’s main research area is computational complexity theory, which concerns itself with the power and limitations of algorithms, according to the statement.
He has co-authored papers with more than 100 people, producing novel connections between mathematics and computer science. His investigations have advanced understanding of questions including: Can creativity be automated? (the P vs. NP question). Can randomness speed up computation? (the BPP vs. P question). Which distributed tasks can be computed privately and securely in adversarial environments? (the foundations of cryptography). What are the power and limitations of communication and interaction?
Such questions, while theoretical in nature, have significant real-world implications, according to the statement. Wigderson’s contributions to the foundations of cryptography have led to the development of protocols as complex as playing a game of poker online, without any physical means. His work on interactive proof systems, in particular the paradoxical notion of zero-knowledge proofs (viewed too impractical to ever be implemented) has recently found its way to blockchain technology and digital currencies. Digital innovations in industry, medicine, online communications, electronic commerce, and the economy, are all underpinned by algorithmic and complexity theoretic research.
Prior to joining the IAS Faculty, Wigderson held academic appointments at the University of California, Berkeley (1983–84); IBM Research, San Jose (1984–85); Mathematical Sciences Research Institute (1985–86); Princeton University (1990–92); and the Hebrew University of Jerusalem (1986–2003), according to the statement.
Wigderson is the recipient of numerous awards, including the Rolf Nevanlinna Prize (1994); Levi L. Conant Prize (2008); Gödel Prize (2009); and Donald E. Knuth Prize (2019). He is currently a member of the American Academy of Arts and Sciences (since 2011) and the National Academy of Sciences (since 2013), according to the statement.