Computer Science – Computational Complexity
Scientific paper
2006-07-31
Theory of Computing 5 (2009) 1, pp. 141-172
Computer Science
Computational Complexity
27 pages; v2:PRW97 strengthening added, references added, typos fixed; v3: fixed error in the proof of the no-signaling theore
Scientific paper
10.4086/toc.2009.v005a008
Consider a game where a refereed a referee chooses (x,y) according to a publicly known distribution P_XY, sends x to Alice, and y to Bob. Without communicating with each other, Alice responds with a value "a" and Bob responds with a value "b". Alice and Bob jointly win if a publicly known predicate Q(x,y,a,b) holds. Let such a game be given and assume that the maximum probability that 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.
No associations
LandOfFree
Parallel repetition: simplifications and the no-signaling case does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Parallel repetition: simplifications and the no-signaling case, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel repetition: simplifications and the no-signaling case will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-33211