MULTI-PROVER ENCODING-SCHEMES AND 3-PROVER PROOF SYSTEMS

Suppose two provers agree in a polynomial p and want to reveal a singl e value y = p(x) to a verifier where x is chosen arbitrarily by the ve rifier. Whereas honest provers should be able to agree on any polynomi al p the verifier wants to be sure that with any (cheating) pair of pr overs the value y he receives is a polynomial function of x. We formal ize this question and introduce multi-prover (quasi-)encoding schemes to solve it. Using multi-prover quasi-encoding schemes we are able to develop new results about interactive proofs. The best previous result appears in [BGLR] and stales the existence of one-round-four-prover i nteractive proof systems for the languages in NP achieving any constan t error probability with O(log n) random bits and poly(log log n) answ er size. We improve this result in two respects. First we decrease the number of provers to three, and then we decrease the answer-size to a constant. Using unrelated (parallel repetition) techniques the same w as independently and simultaneously achieved by [FK] with only two pro vers. When the error-probability is required to approach zero, our tec hnique is more efficient in the number of random bits and in the answe r size. Showing the fast progress in this central topic of theoretical computer science in the short time since these results were achieved Rat's proof of the parallel repetition conjecture [R] lead to further improvements in the parameters of interactive proofs for NF problems. (C) 1996 Academic Press, Inc.