Two prover protocols
Uri Feige, Joe Kilian · 1994
We introduce the miss-match form for two-prover one-round proof systems.Any two-prover one-round proof system can be easily modified so as to be in miss-match form.Proof systems in miss-match form have the projection property that is important for deriving hardness of approximation results for NP-hard combinatorial optimization problems. Our main result is an upper bound on the number of parallel repetitions that suffice in order to reduce the error of miss-match proof systems from p to � .This upper bound depends only on p and on � (polynomial in 1/(1 − p) and in 1/� ).Based on previous work, it follows that for any �> 0, NP has two-prover one-round proof systems with logarithmic-sized questions, constant-sized answers, and error at most � . As part of our proof we prove upper bounds on the influence of random variables on multivariate functions, which may be of independent interest.