Two-Prover Protocols---Low Error at Affordable Rates

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.