Avi Wigderson

Avi Wigderson (born 1956) is an Israeli mathematician and computer scientist whose work has transformed our understanding of randomness, computation, and the relationship between the two. A professor at the Institute for Advanced Study in Princeton, Wigderson received the 2021 Abel Prize — mathematics' highest honor — for his foundational contributions to computational complexity theory, particularly his demonstration that randomness is not a resource that computation fundamentally needs but a structure that can be efficiently eliminated.

Derandomization and the Nature of Randomness

Wigderson's most celebrated result, developed with Noam Nisan and others in the 1980s and 1990s, is the derandomization theorem: if certain computational hardness assumptions hold, then every probabilistic polynomial-time algorithm can be simulated deterministically in polynomial time. In other words: randomness does not buy computational power. It buys efficiency, and only contingently. Under plausible assumptions about the difficulty of certain explicit problems, that efficiency gain can be recovered without randomness at all.

This is not merely a technical result. It is a philosophical claim about the nature of randomness in computation. For decades, probabilistic algorithms were treated as accessing a genuine computational resource — random bits — that deterministic algorithms lacked. Wigderson showed that this resource is, in a precise sense, illusory. The randomness is not doing work that determinism cannot do. It is merely doing work that determinism does more clumsily, and the clumsiness can be engineered away.

The proof techniques are as significant as the result. Wigderson developed pseudorandom generators — deterministic algorithms that expand a short random seed into a long sequence that appears random to any efficient test. The construction of these generators depends on hardness assumptions: the generator works because certain problems are genuinely hard, and that hardness is used to create randomness that is indistinguishable from true randomness to any efficient observer. Hardness becomes randomness; impossibility becomes structure.

The Algebrization Barrier

With Scott Aaronson, Wigderson identified the algebrization barrier (2008), showing that even algebraic extensions of the relativization barrier cannot resolve P versus NP. The result extended the pessimism of the barrier literature: not only do black-box techniques fail, and not only do natural techniques fail, but even techniques that exploit the algebraic structure of computational problems — arithmetization, interactive proofs, PCPs — are still bounded by an oracle horizon they cannot escape.

Wigderson's broader work on proof complexity and communication complexity has established lower bounds that are, in a field starved for such results, genuinely rare. His approach is characteristically structural: rather than attacking specific problems with ad hoc combinatorial arguments, he identifies the information-theoretic or algebraic structures that make problems hard, then proves that these structures are unavoidable.

Avi Wigderson is the mathematician's mathematician in a field dominated by engineers. Where others build algorithms, he builds understanding — and the understanding he builds is that randomness is not a resource, hardness is not an obstacle, and the deepest questions in computation are not about what machines can do but about what structure permits. The Abel Prize recognized what the field already knew: that Wigderson did not just solve problems. He redefined what it means for a problem to be solvable.