David Zuckerman, professor of computer science at The University of Texas at Austin, and Eshan Chattopadhyay, now an associate professor at Cornell University, have been awarded the 2025 Gödel Prize—one of the most prestigious accolades in theoretical computer science. The honor recognizes their paper “Explicit Two-Source Extractors and Resilient Functions”, which represents a landmark solution to a central open problem in randomness extraction.
The Gödel Prize, jointly awarded by ACM SIGACT and the European Association for Theoretical Computer Science, celebrates outstanding research in theoretical computer science. Named after logician Kurt Gödel, it is one of the field’s highest distinctions in computer science—awarded to just one paper annually, sometimes split, for its profound and lasting impact.
Published in 2019, the paper introduced a novel method for constructing explicit two-source extractors—mathematical tools used to generate high-quality randomness from two weakly random sources. Prior to this work, all known constructions required each source to contain nearly half of the total randomness. Chattopadhyay and Zuckerman’s result lowered that requirement dramatically, to just polylogarithmic min-entropy, making progress on a problem that had resisted solution for many years.
“Randomness is essential for cryptography and distributed computing,” said Zuckerman. Beyond extractors, the authors' method yields improved constructions of explicit Ramsey graphs—combinatorial structures central to mathematics and computer science—and introduces a new class of resilient Boolean functions with wide-ranging implications.
Chattopadhyay began exploring related problems during an undergraduate summer internship with ETH Zurich , long before the full breakthrough came into focus.
“Soon after starting graduate school, I discovered the world of extractors and became fascinated,” said Chattopadhyay. “They are beautiful combinatorial objects, and the philosophical questions surrounding randomness were especially captivating.”
“Honestly, it seemed too ambitious of a goal,” he said. “David played a pivotal role during my Ph.D., providing guidance while giving me the freedom to explore and make mistakes. That gave me the confidence to keep pushing, and eventually we hit upon a plausible approach.”
The collaboration hinged on identifying a connection between a method Zuckerman had explored years earlier and new ideas Chattopadhyay had been developing.
“I don’t think I told it to Eshan,” Zuckerman recalled. “He rediscovered it and realized a connection with other work on non-malleable extractors. This made the approach viable.”
“There were several obstacles to overcome,” Zuckerman said. “But we persevered and figured out how to circumvent them. Sometimes not giving up can go a long way.”
“We had a plausible approach, but there was a crucial gap,” Chattopadhyay explained. “I came up with what I thought was a clever fix, quickly wrote up a draft, and sent it to David. The next day, it turned out I had made a key assumption that was completely false. Rather than discard the approach, David focused on constructing a resilient function with the property I had incorrectly assumed—and we were able to do it. That’s when I realized it could actually work.”
David Zuckerman earned his Ph.D. at the University of California, Berkeley and is widely recognized for foundational contributions to pseudorandomness and computational complexity. His contributions have earned the 30-Year Test of Time Award at FOCS 2021 for such lasting impact.
Eshan Chattopadhyay completed his Ph.D. at UT Austin before joining Cornell University, where he now works on pseudorandomness, circuit complexity, and communication complexity. He was named a National Science Foundation CAREER Award recipient in 2021.
“This recognition is truly an incredible honor,” said Chattopadhyay. “The Gödel Prize has celebrated some of the most beautiful and foundational work in our field. It feels surreal—and deeply gratifying—that our paper is being placed in that category.”
The result has already inspired a wave of follow-up research and extensions.
“Previously, most research on randomness extraction focused on seeded extractors,” said Zuckerman. “Now our work—and the works that followed—have demonstrated big advances for two-source extractors and Ramsey graphs. I hope this attracts young talent to the field.”
“This project reinforced for me the value of being curious across different areas of theory,” Chattopadhyay added. “It’s been rewarding to keep building on this work—exploring connections and finding new applications in circuit complexity and beyond.”
“I’m fortunate to now work with wonderful students who are just as excited to push these questions forward.”
Beyond academia, their construction opens new possibilities in cryptographic systems, secure communications, randomized algorithms, and distributed computing.
The 2025 Gödel Prize will be formally awarded at the ACM Symposium on Theory of Computing (STOC), which will be held in Prague this June.
With this achievement, The University of Texas at Austin Computer Science continues to demonstrate leadership in advancing the foundational ideas that shape computing—ideas that begin in theory, but reverberate far beyond.