<p>To get things rolling, I have a potential game and would like feedback.</p>

<p>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 <strong>cycle-power</strong> 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.</p>

<p>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.</p>

<p>I believe this is a good example for two reasons:</p>

<ol>
<li><p>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.</p></li>
<li><p>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.</p></li>
</ol>

<p>Has this game been considered/solved already?</p>

CC BY-SA 2.5
2010-12-16T19:59:17.823Z
2010-12-16T21:56:52.570Z
2010-12-16T21:56:52.570Z
Derrick Stolee
<p>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. </p>

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

<ul>
<li>Barak et al generalized the counterexample of Raz to all unique games with SDP gaps.</li>
<li>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.</li>
</ul>

CC BY-SA 2.5
2010-12-16T21:05:37.713Z
2010-12-16T21:05:37.713Z
Dana Moshkovitz
<p>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 <a href="http://videos.seas.harvard.edu/conferences/ccc10/wed/ranraz.mov?download" rel="nofollow">Ran Raz's survey talk at CCC 2010</a> for an overview of the subject. </p>

<p>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:</p>

<blockquote>
  <p><strong>Theorem</strong>: 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)}$.</p>
</blockquote>

<p>Here is an outline on the work of identifying this constant $c$:</p>

<ul>
<li>Raz's original paper proves $c \leq 32$.</li>
<li><a href="http://cse.unl.edu/~theorysem/Hol07-ParallelRepetitionTheorem.pdf" rel="nofollow">Holenstein</a> improved this to $c \leq 3$.</li>
<li><a href="http://cse.unl.edu/~theorysem/Rao08-ProjectiveParallelRepetition.pdf" rel="nofollow">Rao</a> showed that $c&#39; \leq 2$ suffices (and the dependence on $s$ is removed) for the special case of projection games.</li>
<li><a href="http://cse.unl.edu/~theorysem/Raz08-OddCycleGame.pdf" rel="nofollow">Raz</a> gave a strategy for the odd-cycle game that showed Rao's result is sharp for projection games.</li>
</ul>

<p>By this body of work, we know $2 \leq c\leq 3$.  My two questions are as follows:</p>

<blockquote>
  <p><strong>Question 1:</strong> Do experts in this area
  have a consensus for the exact value
  of $c$?</p>
</blockquote>

<p>If it is thought that $c &gt; 2$, are there specific games which are not projective, but also specifically violate the extra properties of projection games that Rao's proof requires.</p>

<blockquote>
  <p><strong>Question 2:</strong> If $c &gt; 2$, which
  interesting games violate Rao's
  strategy and have a potential to be
  sharp examples?</p>
</blockquote>

<p>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.</p>

<cc.complexity-theory><approximation-hardness>
Which 2P1R Games are Potentially Sharp?
Derrick Stolee
# Which 2P1R Games are Potentially Sharp?

(Asked by: username_0 on 2010-12-16)

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](http://videos.seas.harvard.edu/conferences/ccc10/wed/ranraz.mov?download) 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](http://cse.unl.edu/~theorysem/Hol07-ParallelRepetitionTheorem.pdf) improved this to $c \leq 3$.
* [Rao](http://cse.unl.edu/~theorysem/Rao08-ProjectiveParallelRepetition.pdf) showed that $c' \leq 2$ suffices (and the dependence on $s$ is removed) for the special case of projection games.
* [Raz](http://cse.unl.edu/~theorysem/Raz08-OddCycleGame.pdf) 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.

**Tags:** cc.complexity-theory, approximation-hardness


---

## 2 answers

### Answer by username_1 on 2010-12-16. Score: 8 | Accepted answer

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 by username_0 on 2010-12-16. Score: 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?


---

