<blockquote>
  <p>Does exponential decrease also happen in continuous case?</p>
</blockquote>

<p>No.  Feige and Verbitsky [FV02] showed that for every <i>n</i>, there is a game <i>G</i> (with finite sets of questions and answers) such that <i>v</i>(<i>G</i>)≤3/4 and <i>v</i>(<i>G</i><sup><i>n</i></sup>)≥1/8.  Because your formulation generalizes games with finite sets of questions and answers of any size, parallel repetition (of any finitely many times) cannot decrease the value of a game from 3/4 to 1/8.</p>

<p>[FV02] Uriel Feige and Oleg Verbitsky.  Error reduction by parallel repetition—A negative result.  <em>Combinatorica</em>, 22(4):461–478, Oct. 2002.  <a href="http://dx.doi.org/10.1007/s00493-002-0001-0">doi:10.1007/s00493-002-0001-0</a>.</p>

CC BY-SA 3.0
2011-12-24T04:43:33.640Z
2011-12-24T04:43:33.640Z
Tsuyoshi Ito
<p>Raz's <a href="http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pparal1.ps">Parallel pretition theorem</a> is an important result in PCP, inapproximation, etc. The theorem is fomalized as follows.</p>

<p>A game $G=(\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B},\pi, V)$, where $\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B}$ are finite sets, $\pi$ is a distribution on $\mathcal{S}\times\mathcal{T}$, and predicate  $V:\mathcal{S}\times\mathcal{T}\times\mathcal{A}\times\mathcal{B}\rightarrow\{0,1\}$. Define value of the game $$v(G)=\max_{h_A\in\mathcal{H}_A,h_B\in\mathcal{H}_B}\sum_{s,t}\pi(s,t)V(s,t,h_A(s),h_B(t))$$  And $n$-fold game $G^n=(\mathcal{S}^n,\mathcal{T}^n,\mathcal{A}^n,\mathcal{B}^n,\pi^n, V^n)$. The theorem says if $v(G)\leq 1-\epsilon,$ then $v(G^n)\leq (1-\epsilon^c)^{\Omega(\frac{n}{\log\max\{|A|,|B|\}})}$.</p>

<p>My quesion is what happen if the sets are infinite, in a continuous space. Say if $\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B}$ are subsets of a space, say $R^n$, or more abstract spaces. All the rest are same. Raz's theorem  only gives a trivial upper bound $1$ since the sizes of answer sets are infinite. Obviously $n$-fold value is upper bounded by single copy.  Does exponential decrease also happen in continuous case?  Would it be more interesting to restrict $\mathcal{H}_A,\mathcal{H}_B$ to be collections of continuous functions or $C^{\infty}$ functions or measureable functions?</p>

<cc.complexity-theory><complexity-classes><pcp><interactive-proofs>
Is there a continuous version of parallel repetition theorem
pyao
# Is there a continuous version of parallel repetition theorem

(Asked by: username_0 on 2011-12-23)

Raz's [Parallel pretition theorem](http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pparal1.ps) is an important result in PCP, inapproximation, etc. The theorem is fomalized as follows.

A game $G=(\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B},\pi, V)$, where $\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B}$ are finite sets, $\pi$ is a distribution on $\mathcal{S}\times\mathcal{T}$, and predicate $V:\mathcal{S}\times\mathcal{T}\times\mathcal{A}\times\mathcal{B}\rightarrow\{0,1\}$. Define value of the game $$v(G)=\max\_{h\_A\in\mathcal{H}\_A,h\_B\in\mathcal{H}\_B}\sum\_{s,t}\pi(s,t)V(s,t,h\_A(s),h\_B(t))$$ And $n$-fold game $G^n=(\mathcal{S}^n,\mathcal{T}^n,\mathcal{A}^n,\mathcal{B}^n,\pi^n, V^n)$. The theorem says if $v(G)\leq 1-\epsilon,$ then $v(G^n)\leq (1-\epsilon^c)^{\Omega(\frac{n}{\log\max\{|A|,|B|\}})}$.

My quesion is what happen if the sets are infinite, in a continuous space. Say if $\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B}$ are subsets of a space, say $R^n$, or more abstract spaces. All the rest are same. Raz's theorem only gives a trivial upper bound $1$ since the sizes of answer sets are infinite. Obviously $n$-fold value is upper bounded by single copy. Does exponential decrease also happen in continuous case? Would it be more interesting to restrict $\mathcal{H}\_A,\mathcal{H}\_B$ to be collections of continuous functions or $C^{\infty}$ functions or measureable functions?

**Tags:** cc.complexity-theory, complexity-classes, pcp, interactive-proofs

---

## 1 answers

### Answer by username_1 on 2011-12-24. Score: 8 | Accepted answer

> Does exponential decrease also happen in continuous case?

No. Feige and Verbitsky [FV02] showed that for every *n*, there is a game *G* (with finite sets of questions and answers) such that *v*(*G*)≤3/4 and *v*(*G**n*)≥1/8. Because your formulation generalizes games with finite sets of questions and answers of any size, parallel repetition (of any finitely many times) cannot decrease the value of a game from 3/4 to 1/8.

[FV02] Uriel Feige and Oleg Verbitsky. Error reduction by parallel repetition—A negative result. *Combinatorica*, 22(4):461–478, Oct. 2002. [doi:10.1007/s00493-002-0001-0](http://dx.doi.org/10.1007/s00493-002-0001-0).


---

