Avi Wigderson (Hebrew: אבי ויגדרזון; born 9 September 1956) is an Israeli computer scientist and mathematician. He is the Herbert H. Maass Professor in the school of mathematics at the Institute for Advanced Study in Princeton, New Jersey, United States. His research interests include computational complexity theory, parallel algorithms, graph theory, cryptography, and distributed computing. Wigderson received the Abel Prize in 2021 and the Turing Award in 2023 for his transformative work in theoretical computer science.
Wigderson's work centers on the role of randomness in computation and the structure of efficient algorithms. He is a leading figure in complexity theory, having made pivotal contributions to understanding the power of randomized algorithms, the construction of expander graphs via the zig-zag product, and the foundations of zero-knowledge proofs.
Early life and education
Wigderson was born in Haifa, Israel, on 9 September 1956 to Holocaust survivors. He attended the Hebrew Reali School in Haifa. In 1977, he began his undergraduate studies at the Technion Israel Institute of Technology, where he graduated in 1980. At the Technion, he met his wife, Edna. He subsequently pursued graduate studies at Princeton University, earning a Ph.D. in computer science in 1983. His doctoral dissertation, titled "Studies in Computational Complexity," was supervised by Richard Lipton. Wigderson is credited with vastly enriching the field of computational complexity.
Academic career
After holding short-term positions at the University of California, Berkeley, the IBM Almaden Research Center in San Jose, California, and the Mathematical Sciences Research Institute in Berkeley, Wigderson returned to Israel in 1986 to join the faculty of the Hebrew University of Jerusalem. He received tenure in 1987 and became a full professor in 1991. In 1999, he also took on a position at the Institute for Advanced Study, and in 2003 he relinquished his Hebrew University position to take up the role of Herbert H. Maass Professor at the Institute in Princeton.
At the Institute for Advanced Study, Wigderson has focused on the interplay between computational complexity, mathematics, and cryptography. He has helped lead a generation of researchers in these areas.
Key contributions
Wigderson investigated the fundamental question of whether randomness is needed for efficient computation. With Noam Nisan and Russell Impagliazzo, Wigderson showed that for certain algorithms that rely on random coin flips, there exists an almost as fast deterministic algorithm that does not use randomness, provided certain conditions are satisfied. This line of research, built on the concept of pseudorandomness, is a cornerstone of theoretical computer science.
Working with Omer Reingold and Salil Vadhan, Wigderson developed the zig-zag product, a combinatorial operation on graphs that combines smaller graphs to produce larger, well-connected ones. This concept bridges complexity theory, graph theory, and group theory, with applications ranging from understanding how to navigate a maze to constructing efficient expander graphs. The zigzag product became a major tool in theoretical computer science.
Wigderson, along with Silvio Micali and Oded Goldreich, demonstrated that zero-knowledge proofs can be used to verify public results about secret data without revealing the underlying secrets. This work is a foundational layer for modern cryptography.
Awards and honors
Wigderson received the Nevanlinna Prize in 1994, a prize from the International Mathematical Union, for his work on computational complexity. In 2009, he shared the Godel Prize for the zig-zag construction of graphs. He was elected to the American Academy of Arts and Sciences in 2011 and as an ACM Fellow in 2018 for contributions to theoretical computer science and mathematics.
In 2019, Wigderson earned the Knuth Prize for, among other things, work on randomized computation, circuit complexity, proof complexity, and parallel computation. He received the Abel Prize in 2021 with Laszlo Lovasz for foundational contributions to theoretical computer science and discrete mathematics. In April 2024, the Association for Computing Machinery presented him the Turing Award for reshaping the understanding of randomness in computation and for decades of leadership in theoretical computer science. He was also granted the Carnegie Corporation's Great Immigrant Award in 2025.
Personal life
Wigderson is married to Edna, and they have a son, Yuval, who is a professor of mathematics at the Institute of Science and Technology Austria. Wigderson continues to inspire upcoming researchers through his work and mentorship.