# Is there a constructive parallel repetition theorem for nice MIP protocols?

Theorem 1.1 of Ran Raz's paper is a non-constructive upper bound on the soundness error of parallel repetitions of a 2-prover minimally minimally interactive proof system with perfect completeness.

As far as I can see, despite the second sentence of that paper's abstract suggesting otherwise, that paper does not give a constructive upper bound on the relevant quantities.

Is there a known constructive upper bound on the soundness error of parallel repetitions of a 2-prover minimally minimally interactive proof system with perfect completeness?

• "constructive" is an overloaded term. what do you mean? – Sasho Nikolov Jan 3 '14 at 10:02
• I mean "implicitly gives an algorithm which, on input of a rational number in the interval (0,1) for the soundness error of the original protocol and another such rational for the target soundness error, outputs an integer such that the soundness error of [parallel repetition of that many copies of the original protocol] is at most the target soundness error". $\;$ – user6973 Jan 3 '14 at 21:09
• i.e. you want computable bounds (but not necessarily polynomial time computable)? – Sasho Nikolov Jan 3 '14 at 23:02
• Yes. ${}{}{}\;$ – user6973 Jan 3 '14 at 23:12

In his simplified proof of the parallel repetition theorem, Holenstein gives the following explicit bound on the value of the $n$-fold parallel repetition of a game with value $v$:
$$\left(1-\frac{(1-v)^3}{6000}\right)^{n/\log(|\Sigma_1|\cdot |\Sigma_2|)},$$ where $\Sigma_1, \Sigma_2$ are the alphabets of the two players.
• I'm not referring to any particular step, just the mysterious function $W$. $\:$ Although I only read the first few pages (the paper is over 40 pages), I didn't see him asserting that his bound(s) could be made explicit. $\;\;\;$ – user6973 Jan 4 '14 at 0:52
• Why would you characterize the bound as non-constructive in your question, despite the abstract explicitly claiming constructivity, if you do not know the proof well enough to know whether there is an implicit algorithm to compute $W$? – Sasho Nikolov Jan 4 '14 at 11:21
• The abstract does not explicitly claim constructivity; it strongly suggests constructivity. $\hspace{.53 in}$ On the other hand, the paper explicitly does not focus on the "exact behavior of the function" $W$, and none of the three comments at the top of page 4 imply constructivity. $\hspace{.42 in}$ – user6973 Jan 4 '14 at 11:39