The following Test of Time Awards were given at STOC 2026.

The 30-year Test-of Time award recognizes three seminal papers published in 1996 and 1993.

• "Generating hard instances of lattice problems", Miklós Ajtai (1996)
• "A fast quantum mechanical algorithm for database search" (1996), Lov K. Grover
• "Efficient noise-tolerant learning from statistical queries", Michael J. Kearns (1993)

Ajtai's paper is recognized for the foundational discovery of the worst-case to average-case reduction for lattice problems, for the accompanying construction of a one-way function whose hardness relies on worst-case assumptions, and for establishing lattice problems as rigorous mathematical foundations for modern and post-quantum cryptography.

Grover's paper is recognized for the discovery of a simple quantum search algorithm giving a quadratic speedup for unstructured search, for introducing ideas that became central to amplitude amplification, making Grover's algorithm a fundamental primitive in quantum algorithms.

Kearns's paper is recognized for introducing the statistical query model, showing how many learning algorithms can rely on aggregate statistics rather than individual examples, and for creating a foundational framework for efficient learning in the presence of classification noise.

The 20-year Test-of-Time award recognizes three seminal papers published in 2006 and 2005.

• "Explicit capacity-achieving list-decodable codes", Venkatesan Guruswami and Atri Rudra (2006)
• "The complexity of computing a Nash equilibrium", Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou (2006)
• "Undirected st-connectivity in log-space", Omer Reingold (2005)

Guruswami and Rudra's's paper is recognized for the discovery of the first family of codes achieving list-decoding capacity, thereby introducing foundational techniques and useful black-box results that have had lasting impact on coding theory and theoretical computer science.

Daskalakis, Goldberg, and Papadimitriou's paper is recognized for proving that computing a Nash equilibrium is PPAD-complete, thereby identifying the intrinsic complexity of equilibrium computation and transforming algorithmic game theory by connecting fixed-point theorems, reductions, and computational barriers to a central concept in economics.

Reingold's paper is recognized for resolving the long-standing space complexity of undirected connectivity by giving a deterministic log-space algorithm, establishing SL = L, and introducing graph-powering and derandomized-exploration techniques that became central tools in space-bounded computation.

The 10-year Test-of-Time award recognizes three seminal papers published in STOC 2016:

• "Graph isomorphism in quasipolynomial time", László Babai
• "A cost function for similarity-based hierarchical clustering", Sanjoy Dasgupta
• "Constant-round interactive proofs for delegating computation", Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum

Babai's paper is recognized for achieving a quasipolynomial-time algorithm for graph isomorphism, breaking a barrier that had stood for more than three decades, and introducing a deep synthesis of group theory, combinatorics, and canonical partitioning that reshaped the complexity-theoretic landscape of isomorphism problems.

Dasgupta's paper is recognized for introducing a simple global objective for similarity-based hierarchical clustering, transforming dendrogram construction from a collection of linkage heuristics into an optimization problem, and launching a broad theoretical study of approximation, hardness, and algorithm design for hierarchical clustering.

Reingold, Rothblum, and Rothblum's paper is recognized for showing that broad bounded-space computations admit constant-round public-coin interactive proofs for delegation, with efficient provers and fast verifiers, and for introducing proof-system ideas that influenced later work on succinct, oracle-based, and unconditionally sound verification.

Award Committee:

Ran Canetti (Boston U)
Moses Charikar (chair, Stanford)
Mike Paterson (Warwick)
David Shmoys (Cornell)