Multi-prover Encoding Schemes and Three-prover Proof Systems

摘要

Suppose two provers agree in a polynomialpand want to reveal a single vaiuey=p(x) to a verifier wherexis chosen arbitrarily by the verifier. Whereas honest provers should be able to agree on any polynomialpthe verifier wants to be sure that with any (cheating) pair of provers the valueyhe receives is a polynomial function ofx. We formalize 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 states the existence of one-round-four-prover interactive proof systems for the languages in NP achieving any constant error probability withO(log n) random bits andpoly(log log n) answer 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 was independently and simultaneously achieved by [FK] with only two provers. When the error-probability is required to approach zero, our technique is more efficient in the number of random bits and in the answer size. Showing the fast progress in this central topic of theoretical computer science in the short time since these results were achieved Raz's proof of the parallel repetition conjecture [R] lead to further improvements in the parameters of interactive proofs for NP problems.