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

The 30-year Test-of Time award recognizes three seminal papers that were published in STOC 1990 and 1991:

The Blum-Luby-Rubinfeld paper introduced the concepts of self-testing and self-correction of programs, which allow for efficiently testing the correctness of programs on typical instances and then correcting the programs on arbitrary instances. These concepts spawned the area of property testing (and more generally sublinear-time algorithms) and inspired the interactive proof revolution of the early 1990’s. Moreover, the elegant 3-query linearity test from the paper remains at the core of all constructions of probabilistically checkable proofs.

The Dolev-Dwork-Naor paper introduced the concept of non-malleability in cryptography, whereby an adversary should not be able to modify a ciphertext or protocol transcript based on an unknown message m into one corresponding to a related message m’. Since then non-malleability has become a central concept in the study of cryptographic protocols, playing a key role in understanding whether security is maintained in concurrent environments.

Nisan’s paper gave the first construction of an unconditional pseudorandom generator for logspace computation with polylogarithmic seed length, which was subsequently used to give highly nontrivial derandomizations of randomized space-bounded computation and found applications to other areas, such as streaming algorithms. Despite three decades of intensive research improving Nisan’s generator in special cases, it remarkably remains unbeaten for the case of general logspace computation.

The 20-year Test-of-Time award recognizes two seminal papers that were published in STOC 2002:

Charikar’s paper constructed highly efficient locality-sensitive hash functions by importing rounding techniques developed in approximation algorithms. Specifically, Charikar introduced a sketching scheme for cosine similarity that is widely used in statistics and machine learning for applications ranging from word embeddings in natural-language processing to condensing features in machine learning to collaborative filtering. Charikar also constructed sketches for earthmover distance, which have become a basic tool for the theory of approximation algorithms involving optimal transport.

Khot’s paper introduced the Unique Games Conjecture (UGC), an NP-hardness conjecture about probabilistically checkable proofs with a certain structure. In the following years, the UGC was found to imply tight inapproximability results for many important problems, to be closely tied to the power of semidefinite programming in approximation algorithms, and to lead to progress on mathematical questions in seemingly unrelated areas. A relaxation of the UGC, known as the “Two-to-Two Conjecture,” was recently proven in a sequence of papers of Dinur, Khot, Minzer and Safra.

The 10-year Test-of-Time award recognizes two seminal papers that were published in STOC 2009 and 2012:

The paper by Fiorini et al. resolved a 25-year open problem, proving exponential lower bounds for arbitrary extended formulations of the TSP polytope, as well as for many other NP-hard optimization problems, via a new connection to nondeterministic communication complexity. It also defined and proved the first superpolynomial lower bounds for semidefinite extended formulations. The paper led to a beautiful body of work giving near-optimal inapproximability results for using linear and semidefinite programming hierarchies to solve a variety of NP-complete problems.

Gentry’s paper addressed one of the major open problems in cryptography, namely the construction of a fully homomorphic encryption scheme (FHE), a problem which had dated to 1978. The result and techniques inspired a vast body of follow-up work, including practical implementations, and theoretical works that improved on the security assumptions, asymptotic efficiency, and more. Its ideas of "noisy but controlled" manipulations of lattice based cryptosystems led to the first constructions of cryptographic multilinear maps and schemes for achieving indistinguishability obfuscation of programs.

Award Committee:

Toniann Pitassi (Columbia)
Satish Rao (Berkeley)
Salil Vadhan (Harvard, chair)
Avi Wigderson (Institute for Advanced Study)