ECCC-Report TR14-054https://eccc.weizmann.ac.il/report/2014/054Comments and Revisions published for TR14-054en-usTue, 14 Apr 2015 05:23:10 +0300
Revision 2
| Parallel Repetition From Fortification |
Dana Moshkovitz
https://eccc.weizmann.ac.il/report/2014/054#revision2The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game G^k
in terms of the value of the game G and the number of repetitions k.
Contrary to what one might have guessed the value of G^k is not val(G)^k,
but rather a more complicated expression depending on properties of G.
Indeed, there are numerous works aiming to understand the value of repeated games.
In this work we give a simple transformation on games, which we call "fortification",
and show that for fortified games G, the value of the 2-repeated game is approximately val(G)^2.
Our proof is extremely short and simple.
As a corollary, starting with the combinatorial PCP of Dinur that has soundness error close to 1,
we get a simple, combinatorial, construction of a PCP with soundness error close to 0.
The latter can be used for hardness of approximation as in the work of Hastad. Tue, 14 Apr 2015 05:23:10 +0300https://eccc.weizmann.ac.il/report/2014/054#revision2
Revision 1
| Parallel Repetition of Fortified Games |
Dana Moshkovitz
https://eccc.weizmann.ac.il/report/2014/054#revision1The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game G^k in terms of the value of the game G and the number of repetitions k.
Contrary to what one might have guessed, the value of G^k is not val(G)^k, but rather a more complicated expression depending on properties of G.
Indeed, there are numerous works aiming to understand the value of repeated games, both for general games G and for special cases.
A case of particular interest is that of projection games, where the answer of the first prover determines at most one acceptable answer for the second prover.
In this work we give a simple transformation, which we call "fortification", that can be applied to any projection game.
We show that for fortified games G, the value of the k-repeated game is approximately val(G)^k.
This results in nearly a quadratic improvement in the size of projection PCP with the lowest error known today.
Unlike previous proofs of the parallel repetition theorem that relied on information theory or linear algebra, our proof is purely combinatorial and quite short.
We then discuss the problem of derandomizing parallel repetition, and the limitations of the fortification idea in this setting.
We point out a connection between the problem of derandomizing parallel repetition and the problem of composition.
This connection could shed light on the so-called Projection Games Conjecture, which asks for projection PCP with minimal error. Sat, 26 Apr 2014 16:54:40 +0300https://eccc.weizmann.ac.il/report/2014/054#revision1
Paper TR14-054
| Parallel Repetition of Fortified Games |
Dana Moshkovitz
https://eccc.weizmann.ac.il/report/2014/054The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game G^k in terms of the value of the game G and the number of repetitions k.
Contrary to what one might have guessed, the value of G^k is not val(G)^k, but rather a more complicated expression depending on properties of G.
Indeed, there are numerous works aiming to understand the value of repeated games, both for general games G and for special cases.
A case of particular interest is that of projection games, where the answer of the first prover determines at most one acceptable answer for the second prover.
In this work we give a simple transformation, which we call "fortification", that can be applied to any projection game.
We show that for fortified games G, the value of the k-repeated game is approximately val(G)^k.
This results in nearly a quadratic improvement in the size of projection PCP with the lowest error known today.
Unlike previous proofs of the parallel repetition theorem that relied on information theory or linear algebra, our proof is purely combinatorial and quite short.
We then discuss the problem of derandomizing parallel repetition, and the limitations of the fortification idea in this setting.
We point out a connection between the problem of derandomizing parallel repetition and the problem of composition.
This connection could shed light on the so-called Projection Games Conjecture, which asks for projection PCP with minimal error. Wed, 16 Apr 2014 18:11:53 +0300https://eccc.weizmann.ac.il/report/2014/054