Avi Wigderson and the Second Golden Era of Theoretical Computing
The 2021 Abel Prize has been awarded to Avi Wigderson of the Institute for Advanced Study (IAS) in Princeton, NJ, jointly shared with former IAS Visiting Professor László Lovász of Eötvös Loránd University. The announcement, made on March 17 by the Norwegian Academy of Science and Letters, further cements Wigderson’s reputation as one of the world’s most enduringly influential theorists in the field of computational complexity. Wigderson and Lovász are cited “for their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics.”
Wigderson joined the IAS Faculty in 1999, while a full professor at Hebrew University in Jerusalem. In 2003, he became a full-time scholar at IAS and was named the Herbert H. Maass Professor in the IAS School of Mathematics. His appointment, with the coinciding creation of the Computer Science and Discrete Mathematics program, launched what IAS Director Robbert Dijkgraaf has called the “second golden era of theoretical computing” at the Institute. IAS’s first golden era was led by computer-science pioneer John von Neumann, who headed the Institute’s Electronic Computer Project (ECP) in the 1940s and ’50s and left what Dijkgraaf has called “impossibly big shoes to fill”—until Wigderson arrived.
SAME SHOES, ONLY DIFFERENT
As leader of the ECP project during the early days of computing, von Neumann took IAS in an unusual, engineering-oriented direction. To help bridge the gap between mathematical theory—his forte—and real-world feasibility, von Neumann articulated and widely shared fundamental principles of computer architecture—“von Neumann architecture,” it’s still called—which today are embedded in some two billion computers around the world.
Wigderson’s work, which both complements and contrasts with von Neumann’s, has taken IAS back to the more theoretical orientation that guided the Institute’s creation. His research interests include complexity theory, randomness and cryptography, circuit and proof complexity, and algorithms and optimization. While not focused on near-term applications, Wigderson’s work sheds crucial light on the power—and the limits—of computers and their efficiency. His research on computational complexity and intractability, for instance, explores problems for which no efficient solutions or algorithms exist: problems, in other words, that challenge the capabilities of even the most advanced computers. His explorations at the intersection of randomness and cryptography underlie cyber privacy and security systems widely used in communications, electronic commerce, electronic voting, banking, electrical grids, and other crucial components of the world’s digital infrastructure.
Wigderson has pursued and disseminated his research prolifically: he has authored or co-authored more than 200 scientific articles, survey articles and a recent expository book Mathematics and Computation: A Theory Revolutionizing Technology and Science.
Wigderson’s influence ripples outward not only through his research but also through his profound role in shaping future generations of mathematicians and computer scientists. Over the past three decades, he has supervised dozens of graduate students and mentored over 100 postdoctoral scholars at IAS and, previously, at Hebrew University in Jerusalem, Israel, land of his birth.
FROM BEACH BUM TO BIG IDEAS
Wigderson grew up in Haifa, Israel, one of three sons of parents who were both Holocaust survivors. In a 2019 interview for the Heidelberg Laureate Forum Foundation, he described his youthful self as part “beach bum,” part soccer devotee, and part nerd. He credits his father, an electrical engineer, with sparking a lifelong love of puzzles and of “the art and the magic of solving problems.”
Wigderson’s undergraduate studies in computer science at the Technion–Israel Institute of Technology proved foundational to his interest in computing theory. In Israel, theory and mathematics were highly valued as computing’s foundations—a contrast with some U.S. programs, which were rooted more in engineering. Then, as now, Wigderson was fascinated by “the enormous intellectual challenges in understanding what computation is.” But it was his graduate education at Princeton University—where he earned master’s and doctoral degrees in computer science—that unleashed and channeled his abiding passion for research into fundamental problems and big ideas in computational theory.
At a 2016 IAS symposium honoring Wigderson’s 60th birthday, Dr. Richard Lipton of Georgia Institute of Technology—Wigderson’s Ph.D. advisor at Princeton—described his former student as “a great problem solver,” and much more: a thought-leader who has “created whole chunks of field from the theoretical computer community.”
Wigderson’s career at IAS is uniquely individual, and yet it is clearly of the intellectual house and lineage of John von Neumann. And in decades to come, as-yet unforeseen breakthroughs in fundamental computer theory, in parallel computing, in cryptography, in quantum computing will almost certainly carry forward the intellectual DNA of Avi Wigderson: theorist, problem-solver, mentor, and creator of new fields-within-fields, all in the theoretical-yet-potentially-world-changing field of computational complexity.