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.

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

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.

Fixed a typo in the definition of fortified value.

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.