Analytical approach to parallel repetition

with Irit Dinur. STOC 2014.

PDF

abstract

We propose an analytical framework for studying parallel repetition, a basic product operation for one-round two-player games. In this framework, we consider a relaxation of the value of a game, val+\mathrm{val}_+, and prove that for projection games, it is both multiplicative (under parallel repetition) and a good approximation for the true value.

These two properties imply a parallel repetition bound as val(G⊗k)≈val+(G⊗k)=val+(G)k≈val(G)k. \mathrm{val}(G^{\otimes k}) \approx \mathrm{val}_+(G^{\otimes k}) = \mathrm{val}_+(G)^{k} \approx \mathrm{val}(G)^{k}.

Using this framework, we can also give a short proof for the NP-hardness of Label-Cover(1,δ)(1,\delta) for all δ>0\delta>0, starting from the basic PCP theorem.

We prove the following new results:

  • A parallel repetition bound for projection games with small soundness. Previously, it was not known whether parallel repetition decreases the value of such games. This result implies stronger inapproximability bounds for Set-Cover and Label-Cover.

  • An improved bound for few parallel repetitions of projection games, showing that Raz's counterexample is tight even for a small number of repetitions.

Our techniques also allow us to bound the value of the direct product of multiple games, namely, a bound on val(G1⊗⋯⊗Gk)\mathrm{val}(G_1\otimes \cdots\otimes G_k) for different projection games G1,…,GkG_1,\ldots,G_k.

keywords

  • hardness reduction
  • semidefinite programming