This paper was an inflection point for lattice-based cryptography, helping transform it from a relatively small and fragmented research area into a thriving subfield of cryptography with immense theoretical and practical impact. It showed that cryptography based on lattices can be both efficient and secure under worst-case complexity assumptions, a feat never reached by number-theory based cryptography.
With remarkable foresight, the paper first boldly put forward a conjecture on the worst-case hardness of "algebraically structured" lattices, then rigorously proved that such hardness gives rise to similarly structured average-case hardness, and finally convincingly argued that this structure admits fast implementation on modern microprocessors.
The paper's worst-case, and hence average-case, hardness conjectures have withstood the test of time. The techniques introduced in this paper have evolved and grown to an immense body of work, shaping many future results in the area.
The paper "LT Codes" describes the first implementation of so-called "universal erasure codes", which are almost optimal codes for any channel over which data may be lost under any loss model. More specifically, the paper shows how to realize the powerful "digital fountain" concept introduced in earlier work of Byers, Luby, Mitzenmacher and Rege, whose implementation had proved elusive. The actual implementation is extremely elegant and is a perfect example of the power of analytical techniques from CS theory to shape the design of an important real-world artifact.
The ideas in the paper have been hugely influential in both the academic and the technological worlds. Among its thousands of academic citations are works in CS theory, information theory, network coding, optimal and wireless communications, sensor networks, content distribution and data storage. On the practical side, LT codes and their derivatives have become integral parts of several standards for wired and wireless networks.
This seminal paper proves one of the fundamental theorems of modern computational complexity, the remarkable PCP Theorem. That is, every proof has a robust version only polynomially larger that can be probabilistically verified by reading just a constant number of bits. The probabilistic verifier queries just a constant number of bits, and if the input is in the language, then the verifier always accepts; if it is not in the language, then the verifier rejects with high probability. This was the culmination of a line of work that has been highlighted in recent Test of Time Awards, including the related work of Arora-Safra that is a co-winner of this year's award.
Besides being central to our modern understanding of the class NP, this work has had ramifications for many other areas of TCS, notably hardness of approximation and foundations of cryptography. As observed in the paper, the PCP theorem implies that MAXSNP-hard problems are NP-hard to approximate to within a constant factor, and by work of Feige et al. it also implies that MAX CLIQUE is NP-hard to approximate to within a power of n. The PCP Theorem has had a huge influence on subsequent work on inapproximability, and increasingly tight bounds on the best achievable approximation ratios for problems have been obtained by designing PCPs tailored to particular approximation problems. PCP's are not just a theoretical concept, but are currently being implemented in order to have efficient cryptographic proofs of knowledge as an ingredient in blockchain technology. While this paper was immediately recognized as a breakthrough, its implications are still being explored today, and continually surprise and delight.
This exceptional paper was the first to characterize NP in a form very close to the PCP theorem. Specifically, it characterizes NP as the class of languages whose proofs of membership in the language can be made robust in that they can be probabilistically verified by reading just o(log n) bits. If the input is in the language, then the probabilistic verifier always accepts; if it is not in the language, then it rejects with high probability. This was a major step in a line of work that has been highlighted in recent Test of Time Awards, including the related work of Arora-Lund-Motwani-Sudan-Szegedy that improved the number of queried bits to constant and is a co-winner of this year's award.
Besides being central to our modern understanding of the class NP, the PCP theorem has had ramifications for many other areas of TCS, notably hardness of approximation and foundations of cryptography. By work of Arora et al., the PCP theorem implies that MAXSNP-hard problems are NP- hard to approximate to within a constant factor, and by work of Feige et al. it also implies that MAX CLIQUE is NP-hard to approximate to within a power of n. The PCP Theorem has had a huge influence on subsequent work on inapproximability, and increasingly tight bounds on the best achievable approximation ratios for problems have been obtained by designing PCPs tailored to particular approximation problems. PCP's are not just a theoretical concept, but are currently being implemented in order to have efficient cryptographic proofs of knowledge as an ingredient in blockchain technology. While this paper was immediately recognized as a breakthrough, its implications are still being explored today, and continually surprise and delight.
The 2022 FOCS Test of Time Awards, awarded annually, recognize papers published in the Proceedings of the Annual IEEE Symposium on Foundations of Computer Science. This is the fourth annual award. The target years for the Test of Time Awards in 2022 are for papers presented at the FOCS conferences in 1992, 2002, and 2012, which are each considered for separate awards. While papers in the target years will always be considered by the award committee, in each of these award categories it is possible to nominate FOCS conference papers published up to four conferences earlier than the targeted conference. Thus, papers published at FOCS 89-92 can compete for the award targeting the 1992 conference and similar options are available for the other two awards.
Nominations should be sent by July 31, 2022 to focs2022tot@gmail.com with a subject line of "TOT nomination". Nominations should contain an explanation of the impact of the nominated paper(s), including references to follow-on work. Self-nominations are discouraged.
The winners will be selected by a committee appointed by the FOCS Steering Committee, which for 2022 consists of Russell Impagliazzo (UCSD), Yael Kalai (Microsoft Research and MIT), Alistair Sinclair (UC Berkeley), Éva Tardos (Cornell University), David Zuckerman (UT Austin), and committee chair Michael Saks (Rutgers University).
In selecting the Test of Time Award winners, the Committee will pay particular attention to long-term impact. This impact can come in many forms, including:
The committee expects to select exactly one paper for the award associated with each of the targeted years 1992, 2002 and 2012 conferences. However, the committee may select up to three papers in each category, and include papers from up to four years prior to the targeted year. The committee may give awards to papers that are not nominated.