Skip to content

Avi Wigderson

Abstract

Avi Wigderson (born 1956) is the theorist who settled, as far as it can be settled without proving P ≠ NP, what randomness is worth to a computer: probably nothing. With Noam Nisan in 1988 and Russell Impagliazzo in 1997 he showed that if any problem is as hard as everyone believes some are, then every fast algorithm that flips coins can be replaced by one that does not; the coins are a convenience, not a source of power. Before that, with Oded Goldreich and Silvio Micali, he had shown that every statement in NP has a zero-knowledge proof, which is the theorem the privacy cryptography of the 2010s is built on. He was the first person to receive both the Abel Prize (2021) and the Turing Award (2023), and in forty years at the Hebrew University and the Institute for Advanced Study he has co-authored with several hundred people, which is its own kind of result.

Avi Wigderson
Avi Wigderson in London, 2012. Image: Ednawig, CC BY-SA 3.0, via Wikimedia Commons.

Haifa to Princeton

Avi Wigderson was born in Haifa on September 9, 1956, to parents who had survived the Holocaust; his father, an engineer, taught him mathematics as puzzles. He took a computer-science degree at the Technion in 1980 and a doctorate at Princeton in 1983 under Richard Lipton, with a thesis on computational complexity, then spent three years in postdoctoral positions at Berkeley, IBM Almaden and the Mathematical Sciences Research Institute, the California circuit on which the theory of the 1980s was made. He joined the Hebrew University of Jerusalem in 1986, was a full professor by 1991, and moved to the Institute for Advanced Study in Princeton in 1999, full-time from 2003, where he is Herbert H. Maass Professor in the School of Mathematics.

Zero Knowledge for Everything

Shafi Goldwasser, Silvio Micali and Charles Rackoff had defined the zero-knowledge proof in 1985: a way for a prover to convince a verifier that a statement is true while revealing nothing else (see Shafi Goldwasser and Silvio Micali). They had examples. In 1986 Goldreich, Micali and Wigderson proved the general theorem: assuming one-way functions exist, every statement in NP, which is to say every statement whose proof could be checked efficiently, has a zero-knowledge proof. The construction went through graph three-colouring, with the prover committing to a colouring in sealed envelopes and the verifier opening two adjacent ones at random; the paper’s title says the proofs “yield nothing but their validity”. A companion result the following year showed that any multi-party computation can be done securely, with each party learning only the output. Those two theorems are the reason a blockchain can verify a transaction without seeing it and a hospital can compute a statistic across records nobody shares.

Hardness Against Randomness

The question that occupied him longest was whether randomness helps. Randomised algorithms were fast for problems, primality testing above all, where no fast deterministic method was known, and the complexity class BPP, problems solvable in polynomial time with coin flips and a bounded chance of error, might be strictly larger than P. Wigderson’s programme, in a series of papers from the late 1980s, tied the question to a different one. Nisan and Wigderson (1988, journal version 1994) built a pseudorandom generator from any function that is hard for small circuits: stretch a short truly random seed through the hard function and the output is indistinguishable, to any efficient algorithm, from real randomness, so any algorithm that needs random bits can be run on all seeds and the majority answer taken. Impagliazzo and Wigderson (1997) sharpened the trade: if some problem solvable in exponential time requires circuits of exponential size, an assumption almost every theorist accepts, then P = BPP. Randomness, on this view, is an artefact of our ignorance about which problems are hard, and the coins can be removed the moment that ignorance is repaired. The surrounding story, including the deterministic primality test of 2002 that confirmed the pattern, is in Randomness in Algorithms and P vs NP and Complexity Theory.

The tools built for that programme became a field. Expander graphs, sparse graphs that are nonetheless well connected, are what a pseudorandom generator needs, and the zig-zag product of Reingold, Vadhan and Wigderson (2002) gave a combinatorial way to build them, for which the three received the Gödel Prize in 2009; Reingold used it to show that undirected connectivity can be decided in logarithmic space. Wigderson’s later work runs through communication complexity, proof complexity, the arithmetic of matrices in non-commuting variables, and, with Scott Aaronson in 2009, “algebrization”, a proof that a whole class of techniques cannot separate P from NP.

The Institute

He received the Nevanlinna Prize in 1994, the Knuth Prize in 2019, and in 2021 shared the Abel Prize, mathematics’ equivalent of the Nobel, with László Lovász, for connecting discrete mathematics to computer science. On April 10, 2024, the ACM announced him as the recipient of the 2023 Turing Award, citing foundational contributions to the theory of computation, above all the reshaping of the role of randomness, and decades of intellectual leadership. His book Mathematics and Computation (2019), written for mathematicians who want to know what the theory of computing is, is free on his website, as is most of what he has written. At the Institute he has run the theory group for twenty-five years and is known for having worked with more co-authors than almost anyone in the field; the graph of theoretical computer science in the 2000s has him near its centre.

📚 Sources