Test of Time 1990 Awards

Carsten Lund, Lance Fortnow, Howard J. Karloff, Noam Nisan:
Algebraic Methods for Interactive Proof Systems

This paper produced a breakthrough that fundamentally changed our understanding of the power of interactive proofs, showing that efficient interactive proofs exist for all languages in the polynomial-time hierarchy.

Given previous simulations that had shown how to remove rounds in interactive proofs efficiently and oracle results that had suggested that the existence of efficient interactive proofs even for coNP was unlikely, this power was a surprise.

Its core innovation is a simple and beautiful but powerful algebraic method for interactive verification of the value of the permanent of Boolean matrices, and hence any problem in #P, inspired by previous work on self-testing and self-correction.

The use of algebraic methods for verification protocols is also a core part of subsequent precise characterizations of the power of interactive and multi-prover interactive proofs, as well as the original proofs of the later characterizations of NP in terms of probabilistically checkable proofs.

Adi Shamir:

This paper settled the complexity of Interactive Proof (IP) systems, and in a very surprising way. While it is rather straightforward that IP is included in PSPACE, this paper showed that the trivial inclusion is tight, and IP=PSPACE.

The proof technique applies a very elegant algebraic extension of Boolean first order logical formulas, and uses it to show the equivalence of the two models. It is truly amazing that the entire paper fits in five pages, a true testament to the extreme elegance of the proof technique.

The paper highlighted the importance of Interactive Proof systems for understanding basic concepts in computational complexity. The continued research in this direction has led later to important breakthroughs in our understanding of the hardness of computation.

László Babai, Lance Fortnow, Carsten Lund:
Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols

Greatly extending previous work on interactive proofs for PSPACE problems, the authors show that NEXP can be characterized as the class of languages that admit membership proofs in a model in which two non-communicating provers interact with a probabilistic polynomial time verifier.

Equivalently, the authors show that NEXP can be characterized as the class of problems that admit probabilistically checkable proofs (PCPs) of exponential size that can be checked in polynomial time by a probabilistic verifier that has oracle access to the proof.

Several ideas and techniques introduced in the paper have subsequently become foundational in the theory of probabilistically checkable proofs (PCPs) and its applications to inapproximability. These include the idea of encoding a witness using a low-degree polynomial (in this case, a multilinear polynomial), the development of testing procedures to distinguish valid encodings from oracles that are far from valid encodings, and the development of self-correction procedures that simulate access to a valid encoding given an oracle that is close to a valid encoding.