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 su ce in order to reduce the error of miss-match proof systems from p to epsilon. This upper bound depends only on p and on epsilon (polynomial in 1/(1 - p) and in 1/epsilon). Based on previous work, it follows that for any epsilon > 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.
interactive proof systems complexity theory