Avi Wigderson
Photo Credit: Peter Badge

Birthdate: September 9, 1956
NJ Town Affiliation: Princeton

When Avi Wigderson began his academic career in the late 1970s, the theory of ‘computational complexity’ – which concerns itself with the speed and efficiency of algorithms – was in its infancy. Avi’s contribution to enlarging and deepening the field is arguably greater than that of any single other person, and what was a young subject is now an established field of both mathematics and theoretical computer science. Computational complexity has also become unexpectedly important, providing the theoretical basis for internet security.

Born in Haifa, Israel, in 1956. Avi entered the Technion, the Israeli Institute of Technology, in 1977, and graduated with a B.Sc. in Computer Science in 1980. He moved to Princeton for his graduate studies, receiving his PhD in 1983 for the thesis Studies in Combinatorial Complexity.

In the 1970s, computer theoreticians framed certain fundamental ideas about the nature of computation, notably the notions of P and NP. P is the set of problems that computers can solve easily, say, in a few seconds, whereas NP also contains problems that computers find hard to solve, meaning that the known methods can only find the answer in, say, millions of years. The question of whether all these hard problems can be reduced to easy ones, that is, whether or not P = NP, is the foundational question of computational complexity. Indeed, it is now considered one of the most important unsolved questions in all of mathematics.

Wigderson made stunning advances in this area by investigating the role of randomness in aiding computation. Some hard problems can be made easy using algorithms in which the computer flips coins during the computation. If an algorithm relies on coin-flipping, however, there is always a chance that an error can creep into the solution. Wigderson, first together with Noam Nisan, and later with Russell Impagliazzo, showed that for any fast algorithm that can solve a hard problem using coin-flipping, there exists an almost-as-fast algorithm that does not use coin-flipping, provided certain conditions are met.

Avi has conducted research into every major open problem in complexity theory. In many ways, the field has grown around him, not only because of his breadth of interests, but also because of his approachable personality and enthusiasm for collaborations. He has co- authored papers with well over 100 people, and has mentored a large number of young complexity theorists. “I consider myself unbelievably lucky to live in this age,” he says. “[Computational complexity] is a young field. It is a very democratic field. It is a very friendly field, it is a field that is very collaborative, that suits my nature. And definitely, it is bursting with intellectual problems and challenges.”

In 1999 Avi joined the Institute for Advanced Study and founded the Computer Science and Discrete Mathematics Program. Avi is known for his ability to see links between apparently unrelated areas. He has deepened the connections between mathematics and computer science. One example is the ‘zig- zag graph product’, which he developed with Omer Reingold and Salil Vadhan, which links group theory, graph theory and complexity theory, and has surprising applications such as how best to get out of a maze.

Wigderson has won many prizes including the Nevanlinna, Conant, Gödel, Knuth, and Abel Prize. Avi was honored with the 2023 A.M. Turing Award, considered to be the “Noble Prize of Computing”.

Avi Wigderson is married to Edna, whom he met at the Technion. They have three children, and two grandchildren.