Two-prover one-round (2P1R) games are an essential tool for hardness of approximation. Specifically, the parallel repetition of two-prover one-round games gives a way to increase the size of a gap in the decision version of an approximation problem. See Ran Raz's survey talk at CCC 2010 for an overview of the subject.
The parallel repetition of a game has the astonishing property that while a randomized verifier operates independently, the two players can play the games in a non-independent way to achieve better success than playing each game independently. The amount of success is bounded above by the parallel repetition theorem of Raz:
Theorem: There exists a universal constant $c$ so that for every 2P1R game $G$ with value $1-\epsilon$ and answer size $s$, the value of the parallel repetition game $G^n$ is at most $(1-\epsilon^c)^{\Omega(n/s)}$.
Here is an outline on the work of identifying this constant $c$:
- Raz's original paper proves $c \leq 32$.
- Holenstein improved this to $c \leq 3$.
- Rao showed that $c' \leq 2$ suffices (and the dependence on $s$ is removed) for the special case of projection games.
- Raz gave a strategy for the odd-cycle game that showed Rao's result is sharp for projection games.
By this body of work, we know $2 \leq c\leq 3$. My two questions are as follows:
Question 1: Do experts in this area have a consensus for the exact value of $c$?
If it is thought that $c > 2$, are there specific games which are not projective, but also specifically violate the extra properties of projection games that Rao's proof requires.
Question 2: If $c > 2$, which interesting games violate Rao's strategy and have a potential to be sharp examples?
From my own reading, it seems the most important property of projection games that Rao uses is that a good strategy for parallel repetition would not use many of the possible answers for certain questions. This is somehow related to the locality of projection games.