Analytical approach to parallel repetition

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 2-person games (91A05) Games involving graphs (91A43)

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,

m a t h r m {v a l}_{+}

, 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

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, d e l t a)

for all

d e l t a > 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

m a t h r m v a l (G_{1} o t i m e s ... o t i m e s G_{k})

for different projection games

G_{1}, ..., G_{k}

.

Recommendations

Cites work

Cited in

(only showing first 100 items - show all)

Describes a project that uses

Uses Software

SuLQ

This page was built for publication: Analytical approach to parallel repetition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259598)