Two-Prover Protocols---Low Error at Affordable Rates
Uriel Feige, Joe Kilian · SIAM Journal on Computing · 2000
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 $\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 $\epsilon$. As part of our proof we prove upper bounds on the influence of random variables on multivariate functions, which may be of independent interest.