The 2025 Gödel Prize is awarded to:

• Eshan Chattopadhyay and David Zuckerman, “Explicit two-source extractors and resilient functions”, STOC 2016 and Annals of Mathematics 189(3):653-705, 2019.

Chattpadhyay and Zuckerman’s paper constructs an explicit two-source extractor with polylogarithmic min-entropy, resolving a central problem in the theory of computation that had been open for almost three decades. More conceptually, the extractor takes two independent sources of imperfect randomness and combines them into one nearly-uniform random bit.

One key and novel idea in Chattopadhyay and Zuckerman's construction is the use of a resilient function. Resilient functions were originally introduced in distributed computing by Ben-Or and Linial (1985), and their use in randomness extractors was unexpected. To make their construction work, Chattopadhyay and Zuckerman needed to come up with a novel explicit resilient function that is monotone, computable by an AC0 circuit, and achieves better resilience parameters than previous constructions. The two-source extractor is obtained by composing their resilient function with two other ingredients, a seeded non-malleable extractor and an oblivious sampler. The analysis of the extractor makes essential use of Braverman’s celebrated result that polylog-wise independence fools AC0 circuits, forging a connection between two sub-areas of pseudorandomness that were not previously thought to be connected.

Award Committee:

Mikołaj Bojańczyk (University of Warsaw)
Artur Czumaj (University of Warwick)
Yuval Ishai (Technion)
Anna Karlin (University of Washington)
Marta Kwiatkowska (University of Oxford)
Tim Roughgarden (Columbia University, chair)