Name
Abstract | ||
|---|---|---|
We propose an analytical framework for studying parallel repetition, a basic product operation for one-round twoplayer games. In this framework, we consider a relaxation of the value of projection games. We show that this relaxation is multiplicative with respect to parallel repetition and that it provides a good approximation to the game value. Based on this relaxation, we prove the following improved parallel repetition bound: For every projection game G with value at most ρ, the k-fold parallel repetition G⊗k has value at most [EQUATION] This statement implies a parallel repetition bound for projection games with low value ρ. Previously, it was not known whether parallel repetition decreases the value of such games. This result allows us to show that approximating set cover to within factor (1 --- ε) ln n is NP-hard for every ε > 0, strengthening Feige's quasi-NP-hardness and also building on previous work by Moshkovitz and Raz. In this framework, we also show improved bounds for few parallel repetitions of projection games, showing that Raz's counterexample to strong parallel repetition is tight even for a small number of repetitions. Finally, we also give a short proof for the NP-hardness of label cover(1, δ) for all δ > 0, starting from the basic PCP theorem. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2591796.2591884 | STOC |
Keywords | DocType | Volume |
parallel repetition,one-round two-player games,operator norms,copositive programming,label cover,general,set cover,hardness of approximation | Journal | abs/1305.1979 |
Citations | PageRank | References |
107 | 3.59 | 24 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Irit Dinur | 1 | 1187 | 85.67 |
| David Steurer | 2 | 934 | 44.91 |