Avi Wigderson (Hebrew: אבי ויגדרזון; born September 9, 1956) is an Israeli computer scientist and mathematician. He holds the Herbert H. Maass Professorship in the School of Mathematics at the Institute for Advanced Study in Princeton, New Jersey, United States of America. His research focuses on complexity theory, parallel algorithms, graph theory, cryptography, and distributed computing. Wigderson received the Abel Prize in 2021 for his work in theoretical computer science. He also received the 2023 Turing Award for his contributions to the understanding of randomness in the theory of computation.
Early life and studies
Avi Wigderson was born in Haifa, Israel, to Holocaust survivors. He graduated from the Hebrew Reali School in Haifa. He started his undergraduate studies at the Technion in Haifa in 1977 and graduated in 1980. At the Technion, he met his wife, Edna. He continued his graduate studies at Princeton University, where he earned his Ph.D. in computer science in 1983. His dissertation, titled "Studies in computational complexity," was completed under the guidance of Richard Lipton. He is known for greatly expanding the field of computational complexity.
Academic career
After working briefly at the University of California, Berkeley, the IBM Almaden Research Center in San Jose, California, and the Mathematical Sciences Research Institute in Berkeley, he returned to Israel and joined the teaching staff at the Hebrew University in 1986. He was given a permanent position in 1987 and became a full professor in 1991. In 1999, he also worked at the Institute for Advanced Study, and in 2003, he left his position at the Hebrew University to live full-time at the IAS.
Wigderson studied problems related to computing, especially how chance affects outcomes in this field. Wigderson, along with Noam Nisan and Russell Impagliazzo, found that for algorithms that solve problems using random choices, there is another algorithm that works almost as quickly without using random choices, as long as certain conditions are met.
Wigderson created the Zig Zag product with Omer Reingold and Salil Vadhan. The Zig Zag product connects different areas of mathematics, such as complexity theory, graph theory, and group theory. For example, the Zig Zag product can help someone understand how to find their way out of a maze. Today, complexity theory is used in keeping information safe.
Wigderson, along with Silvio Micali and Oded Goldreich, showed that zero-knowledge proofs can be used to prove facts about secret information without revealing the information itself.
Personal life
Yuval Wigderson is the son of Wigderson and is a professor of mathematics at the Institute of Science and Technology Austria.
Awards and honors
- 1994: Received the Nevanlinna Prize for his work on computational complexity.
- 2009: Won the Gödel Prize for developing the zig-zag product of graphs, a method to combine smaller graphs into larger ones used in building expander graphs.
- 2011: Elected as a member of the American Academy of Arts and Sciences.
- 2018: Named an ACM Fellow for contributions to theoretical computer science and mathematics.
- 2019: Received the Knuth Prize for contributions to "the foundations of computer science in areas including randomized computation, cryptography, circuit complexity, proof complexity, parallel computation, and understanding fundamental graph properties."
- 2021: Shared the Abel Prize with László Lovász for their foundational contributions to theoretical computer science and discrete mathematics, and their role in making these fields central to modern mathematics.
- April 2024: Awarded the Turing Award by the Association for Computing Machinery for "reshaping our understanding of the role of randomness in computation, and for decades of intellectual leadership in theoretical computer science."
- 2025: Received the Carnegie Corporation of New York Great Immigrant Award.