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.