Avi Wigderson Receives 2023 ACM A.M. Turing Award
Press Contact
Avi Wigderson, Herbert H. Maass Professor in the Institute for Advanced Study’s School of Mathematics, was named by the Association for Computing Machinery (ACM) as the recipient of the 2023 ACM A.M. Turing Award, often referred to as the "Nobel Prize of Computing." With this honor, Wigderson has become the first person to receive both a Turing Award and the Abel Prize, widely considered to be the highest recognition for lifetime achievement in mathematics.
The Turing award recognizes Wigderson’s foundational contributions to the theory of computation, which include reshaping understanding of the role of randomness in computation, and decades of intellectual leadership in theoretical computer science.
"I am excited that the ACM has again recognized with this award the theory of computation community, which has contributed so much to computing practice and technology," said Wigderson. "I feel lucky to be part of this extremely dynamic community, whose fundamental goals have deep conceptual, intellectual, and scientific meaning, well beyond practical motivations. My four decades in this field have been a continuous joyride, with fun problems, brilliant researchers, and many students, postdocs, and collaborators who have become close friends." An invitation to the important field and its many parts is available in Wigderson’s book Mathematics and Computation, which is freely available from his website.
At IAS, Wigderson leads a program in Computer Science and Discrete Mathematics (CSDM), which was formally established in 1999 with his appointment to the permanent Faculty. However, the Institute’s history as a leading center for computational research stretches back far beyond this. The Electronic Computer Project (ECP), led by founding IAS Faculty John von Neumann, resulted in the construction of one of the world’s first stored-program computers on the Institute’s campus. The computer produced by the ECP was the practical realization of the mathematical foundations of computing articulated by British mathematician Alan M. Turing, after whom the ACM A.M. Turing Award is named. Von Neumann has also made many theoretical contributions to understanding computation in cellular automata, fault-tolerant circuits, and the brain.
"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 David Nirenberg, IAS Director and Leon Levy Professor. "Avi has continued that tradition at the Institute for the past quarter century, and I am delighted to congratulate him on the 2023 ACM A.M. Turing Award, which recognizes his many contributions to the theoretical foundations of computer science."
Wigderson’s key contributions have enhanced understanding of the role of randomness and pseudorandomness in computation. Computer scientists have discovered a remarkable connection between randomness and computational difficulty (i.e., identifying natural problems that have no efficient algorithms). Working with colleagues, Wigderson authored a highly influential series of works on trading hardness for randomness. They proved, under standard and widely believed computational assumptions, that every probabilistic polynomial time algorithm can be efficiently derandomized (namely, made fully deterministic). In other words, randomness is not necessary for efficient computation. This sequence of works revolutionized the ways in which computer scientists think about randomness, ideas which were applicable to many areas of theoretical computer science.
"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, a past IAS Visiting Professor (2021), and a 2012 A.M. Turing Award Laureate. "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."
In addition to these groundbreaking technical contributions, Wigderson is recognized as an esteemed mentor and colleague, who has advised countless young researchers.
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, Berkeley (1985–86); Princeton University (1990–92); and the Hebrew University of Jerusalem (1986–2003).
Wigderson is the recipient of numerous other awards, including the Rolf Nevanlinna Prize (1994); Levi L. Conant Prize (2008); Gödel Prize (2009); Donald E. Knuth Prize (2019); Abel Prize (2021); and Edsger W. Dijkstra Prize in Distributed Computing (2023). He is currently a Fellow of the ACM (since 2018) and a member of the American Academy of Arts and Sciences (since 2011) and the National Academy of Sciences (since 2013).
About the Institute
The Institute for Advanced Study has served as one of the leading independent centers for theoretical research and intellectual inquiry since its establishment in 1930, advancing the frontiers of knowledge across the sciences and humanities. From founding IAS Faculty Albert Einstein, Erwin Panofsky, and John von Neumann to influential figures Emmy Noether, George Kennan, and J. Robert Oppenheimer to the foremost thinkers of the present, IAS is dedicated to enabling independent inquiry and fundamental discovery.
Each year, the Institute welcomes more than 250 of the world’s most promising post-doctoral researchers and scholars who are selected and mentored by a permanent Faculty, each of whom are preeminent leaders in their fields. Among present and past Faculty and Members, there have been 35 Nobel Laureates, 44 of the 62 Fields Medalists, and 23 of the 27 Abel Prize Laureates, as well as winners of the Pulitzer Prize in History; the Wolf, Holberg, and Kluge prizes; and many MacArthur and Guggenheim fellows, among other honors.
