Advertisement
Published in:
2009 | OriginalPaper | Chapter
Strong Parallel Repetition Theorem for Free Projection Games
Authors : Boaz Barak, Anup Rao, Ran Raz, Ricky Rosen, Ronen Shaltiel
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The parallel repetition theorem states that for any two provers one round game with value at most 1 −
ε
(for
ε
< 1/2), the value of the game repeated
n
times in parallel is at most (1 −
ε
3
)
Ω(
n
/log
s
)
where
s
is the size of the answers set [Raz98],[Hol07]. For
Projection Games
the bound on the value of the game repeated
n
times in parallel was improved to (1 −
ε
2
)
Ω(
n
)
[Rao08] and was shown to be tight [Raz08]. In this paper we show that if the questions are taken according to a product distribution then the value of the repeated game is at most (1 −
ε
2
)
Ω(
n
/log
s
)
and if in addition the game is a
Projection Game
we obtain a
strong parallel repetition
theorem, i.e., a bound of (1 −
ε
)
Ω(
n
)
.