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:

- “Self-testing/correcting with applications to numerical problems" by Manuel Blum, Michael Luby, Ronitt Rubinfeld (1990);
- “Non-malleable cryptography” by Danny Dolev, Cynthia Dwork, and Moni Naor (1991); and
- “Pseudorandom generators for space-bounded computation” by Noam Nisan (1990).

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:

- “Similarity estimation techniques from rounding algorithms” by Moses S. Charikar (2002); and
- “On the power of unique 2-prover 1-round games” by Subhash Khot (2002).

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:

- “Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds” by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf (2012); and
- “Fully homomorphic encryption using ideal lattices” by Craig Gentry (2009).

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)