"Interactive Proofs and the Hardness of Approximating Cliques". Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. Journal of the ACM 43 (1996), 268-292.
"Probabilistic Checking of Proofs: A New Characterization of NP". Sanjeev Arora and Shmuel Safra. Journal of the ACM 45 (1998), 70-122.
"Proof Verification and the Hardness of Approximation Problems". Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Journal of the ACM 45 (1998), 501-555.
In these three pathbreaking papers, the nine authors have developed a completely new understanding of when an algorithmic problem is "intrinsically hard". To clarify this is a central task of theoretical computer science. The basic idea of describing hard problems goes back to Kurt Gödel and is captured today in a problem class named NP. The first fundamental contribution of the prize winners is a description of NP by a new model of computation which integrates the idea of interacting computing agents and randomized computation. The authors obtained the remarkable and far-reaching result that the correctness of a solution can be checked by inspecting only very few bits of it when these bits are chosen at random. The second and equally strong contribution is concerned with a standard approach to solve hard problems, namely by allowing approximative solutions which would be easier to compute. The prize winners established the surprising fact that certain problems in NP remain hard even when only an approximative solution is required. With their deep insights and powerful results, they have opened new perspectives for many problems in computer science, for example in optimization and cryptography.