Score:1

Why I always obtain this soundness bound in parallel repetition of interactive proof systems

in flag

Fix an interactive proof system $(P,V)$ and denote by $(P_k,V_k)$ an interactive proof system in which the parties play in parallel $k$ copies of $(P,V)$ and for which $V_k$ accepts if and only if $V$ would have accepted in all $k$ copies. The Parallel Repetition Theorem says that given a prover $P$ and input $x$ to the proof system: $$\text{If } \Pr[(P^*,V)(x)=1] \leq \epsilon, \text{ then } \Pr[(P^*,V_k)(x)=1] \leq \epsilon^k.$$ However, I do not understand why this should hold true in the (worst) case that $P^*$ plays with $V_k$ $k-1$ "good" copies of $(P,V)$ and $1$ "bad" copy. Shouldn't the soundness bound in that case be $\epsilon^2 < \Pr[(P^*,V_k)(x)=1] \leq \epsilon$?

Marc Ilunga avatar
tr flag
What "flavor" of parallel repetition is this? Is the prover required to succeed in all instances? (Which seems to be the case).
Bean Guy avatar
in flag
@MarcIlunga Yeah, I forgot to mention that. I edited the text, so you are right.
Score:1
tr flag

Assuming we are not too concerned by the constraints of computational proof systems, parallel repetition emulates $k$ independent interactions, and the parallel verifier accepts only if all interactions are accepting.

For this validation strategy (contrasting with the worst-case scenario of the question) and assuming the independence condition, the soundness error is similar to the probability of $k$ successes in $k$ repeated Bernoulli trials, which gives the desired soundness error of $\epsilon^k$.

For considerations on other types of interactive proofs: see here.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.