13
$\begingroup$

Raz's Parallel pretition theorem 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?

$\endgroup$
8
$\begingroup$

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(Gn)≥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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.