1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ "constructive" is an overloaded term. what do you mean? $\endgroup$ – Sasho Nikolov Jan 3 '14 at 10:02
  • 1
    $\begingroup$ 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". $\;$ $\endgroup$ – user6973 Jan 3 '14 at 21:09
  • $\begingroup$ i.e. you want computable bounds (but not necessarily polynomial time computable)? $\endgroup$ – Sasho Nikolov Jan 3 '14 at 23:02
  • $\begingroup$ Yes. ${}{}{}\;$ $\endgroup$ – user6973 Jan 3 '14 at 23:12
1
$\begingroup$

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.

It's not clear to me that Raz's bound is not constructive in your sense; I am wondering what step in his proof you think is not computable. He does not make his bound fully explicit, but I thought this was done more for exposition.

$\endgroup$
  • $\begingroup$ 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. $\;\;\;$ $\endgroup$ – user6973 Jan 4 '14 at 0:52
  • $\begingroup$ 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$? $\endgroup$ – Sasho Nikolov Jan 4 '14 at 11:21
  • $\begingroup$ 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}$ $\endgroup$ – user6973 Jan 4 '14 at 11:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy