Which 2P1R Games are Potentially Sharp?

Question

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.

Answer 1

I tend to believe that c=3 is the right answer for the general case, and that it should be possible to give an example. I'll have to think more about that to know for sure. It's a good question, and I don't know of existing work about it.

Research recently focused on which types of games have (best possible) c=1, mostly because of possible applications to amplification of unique games.

• Barak et al generalized the counterexample of Raz to all unique games with SDP gaps.
• Raz and Rosen showed that for expanding projection games c=1. There are also previous results by a super-set of those authors for free games.

Answer 2

To get things rolling, I have a potential game and would like feedback.

Let $k \geq 2$ be an integer and $m$ be an integer at least $3k+1$ with $m \not\equiv 0 {\pmod {k+1}}$. The cycle-power game is the 2P1R game where the provers attempt to convince the verifier that the graph $C_{m}^k$ is $k+1$ colorable. Here, $C_m^k$ is the graph with vertices given by integers modulo $m$ with edges if the mod-$m$ distance is at most $k$. If there is a $k+1$-coloring of $C_m^{k}$, it must be given by choosing an ordering of $\{1,\dots,k\}$ and coloring the numbers $\{0,\dots,m-1\}$ in this order, since each set of sequential $k+1$ integers in $\{0,\dots,m-1\}$ form a clique. Since $m$ is not a multiple of $k+1$, there will be some point where this coloring fails.

The verifier either asks for a single vertex from both players, to verify that the colors match, or asks for an edge to verify that the colors are different.

I believe this is a good example for two reasons:

1. It is similar enough to the odd-cycle game that a strategy could be built similar to Raz's lower bound. An important part of this strategy is to randomly choose colorings across the repetitions using shared randomness.

2. By randomizing the permutations used in the randomly generated colorings, the number of answers given at each vertex span the entire answer set in a uniform way, attacking Rao's strategy.

Has this game been considered/solved already?