Guruswami Receives Test of Time Awards at STOC and CCC 2026

We’re delighted to share that Simons Institute Director Venkatesan Guruswami has been honored this summer with two 2026 Test of Time Awards for papers that transformed coding theory and pseudorandomness, and emerged from a common algebraic core. 

At the ACM Symposium on the Theory of Computing (STOC) 2026 in June, Guruswami and Atri Rudra received the 20-Year Test of Time Award for their paper, “Explicit Capacity-Achieving List-Decodable Codes,” which was originally presented at STOC 2006. The paper constructed folded Reed–Solomon codes, the first family of error-correcting codes that achieve list-decoding capacity, allowing recovery from the absolute maximum fraction of worst-case errors that information theory allows. The award citation recognizes the breakthrough itself, as well as the foundational techniques and black-box results it introduced, which have had lasting impact on coding theory and theoretical computer science. 

The inaugural Test of Time Award of the Computational Complexity Conference (CCC), presented this week at CCC 2026, honors the paper, “Unbalanced Expanders and Randomness Extractors from Parvaresh–Vardy Codes,” by Guruswami, Chris Umans, and Salil Vadhan. The paper, which received CCC’s Best Paper Award when it was originally presented there in 2007, turned algebraic list-decoding ideas into near-optimal constructions of unbalanced expanders — bipartite graphs with exceptional vertex expansion — and used them to build powerful randomness extractors that distill nearly uniform random bits from weak sources. 

The common thread in the two papers is the algebra of correlated polynomial evaluations. In the STOC paper, this structure pushed error correction to the information-theoretic limit; in the CCC paper, it became a source of expansion and pseudorandomness. Together, the two results illustrate how a deep insight in one field can unlock seemingly distant problems. Another striking example came earlier this summer: the breakthrough placing bipartite matching in deterministic NC (the class of problems that can be solved efficiently in parallel) also draws, surprisingly, on folded Reed–Solomon codes and the subspace-design ideas they inspired.

Please join us in congratulating Venkat, Atri, Chris, and Salil!