Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR14-054 | 14th April 2015 05:23

Parallel Repetition From Fortification

RSS-Feed




Revision #2
Authors: Dana Moshkovitz
Accepted on: 14th April 2015 05:23
Downloads: 333
Keywords: 


Abstract:

The 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.



Changes to previous version:

- The proof of parallel repetition in this version is simpler and extremely short.
- A problem in the fortification lemma is fixed in this version.


Revision #1 to TR14-054 | 26th April 2014 16:54

Parallel Repetition of Fortified Games





Revision #1
Authors: Dana Moshkovitz
Accepted on: 26th April 2014 16:54
Downloads: 712
Keywords: 


Abstract:

The 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.



Changes to previous version:

Fixed a typo in the definition of fortified value.


Paper:

TR14-054 | 16th April 2014 15:01

Parallel Repetition of Fortified Games





TR14-054
Authors: Dana Moshkovitz
Publication: 16th April 2014 18:11
Downloads: 1302
Keywords: 


Abstract:

The 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.



ISSN 1433-8092 | Imprint