Parallel repetition: simplifications and the no-signaling case

By Thomas Holenstein. 2006

258 citations recorded by the source corpus.

Consider a game where a refereed chooses (x,y) according to a publiclyknown distribution PXY, sends x to Alice, and y to Bob. Withoutcommunicating with each other, Alice responds with a value "a" and Bobresponds with a value "b". Alice and Bob jointly win if a publiclyknown predicate Q(x,y,a,b) holds. Let such a game be given and assume that the maximum probabilitythat Alice and Bob can win is v<1. Raz (SIAM J. Comput. 27, 1998)shows that if the game is repeated n times in parallel, then the probability that Alice and Bob win all games simultaneously is at most v'(n/log(s)), where s is the maximal number of possible responses from Alice and Bob in the initial game, and v' is a constant depending only on v. In this work, we simplify Raz's proof in various ways and thus shorten it significantly. Further we study the case where Alice and Bob are not restricted to local computations and can use any strategy which does not imply communication among them.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Multi-Agent Common Knowledge Reinforcement Learning (2018, methodology): “In order to minimize the probability of disagreement during decentralized group action selection, agents in G can perform optimal correlated sampling based on a shared random seed (Holenstein, 2007; Bavarian et al., 2016).”
Inference Under Information Constraints II: Communication Constraints and Shared Randomness (2019, background): “Starting with [25] and [47] where the problem of generating shared randomness from correlated randomness and vice-versa, respectively, were considered, several important variants have been studied such as correlated sampling [11], [16], [34], [38] and noninteractive simulation [20], [27], [36].”
Fully device independent quantum key distribution (2012, methodology): “(Similar tools were already used by Holenstein in his derivation of a parallel repetition theorem for the case of two-player games with no-signalling players [Hol09].)”
The Limits of Two-Party Differential Privacy (2010, unknown): “Compression is implemented using privacy-preserving consistent sampling [18], [19] and has a negligible probability of failure (which affects accuracy, not privacy).”
Large Violation of Bell Inequalities with Low Entanglement (2010, background): “Some examples of this are the study of hardness of approximation of the quantum value (commonly called entangled value) of games ([39],[31]), the unique game conjecture in the quantum context ([41]) or the parallel repetition theorem ([30], [41], [20], [40]).”