TY - GEN
T1 - A counterexample to strong parallel repetition
AU - Raz, Ran
PY - 2008
Y1 - 2008
N2 - The parallel repetition theorem states that for any two-prover game, with value 1 - ε (for, say, ε ≤ 1/2), the value of the game repeated in parallel n times is at most (1 - εc)Ω(n/s), where s is the answers' length (of the original game) and c is a universal constant [13]. Several researchers asked wether this bound could be improved to (1 - ε)Ω(n/s); this question is usually referred to as the strong parallel repetition problem. We show that the answer for this question is negative. More precisely, we consider the odd cycle game of size m; a two-prover game with value 1 - 1/2m. We show that the value of the odd cycle game repeated in parallel n times is at least 1 - (1/m) · O(√n). This implies that for large enough n (say, n ≥ Ω(m2)), the value of the odd cycle game repeated in parallel n times is at least (1 - 1/4m2)O(n). Thus: 1. For parallel repetition of general games: the bounds of (1 - εc)Ω(n/s) given in [13, 7] are of the right form, up to determining the exact value of the constant c ≥ 2. 2. For parallel repetition of XOR games, unique games and projection games: the bounds of (1 - ε2)Ω(n) given in [5] (for XOR games) and in [12] (for unique and projection games) are tight. 3. For parallel repetition of the odd cycle game: the bound of 1- (1/m) · Ω̃(√n) given in [5] is almost tight. A major motivation for the recent interest in the strong parallel repetition problem is that a strong parallel repetition theorem would have implied that the unique game conjecture is equivalent to the NP hardness of distinguishing between instances of Max-Cut that are at least 1 - ε2 satisfiable from instances that are at most 1 - (2/π) · ε satisfiable. Our results suggest that this cannot be proved just by improving the known bounds on parallel repetition.
AB - The parallel repetition theorem states that for any two-prover game, with value 1 - ε (for, say, ε ≤ 1/2), the value of the game repeated in parallel n times is at most (1 - εc)Ω(n/s), where s is the answers' length (of the original game) and c is a universal constant [13]. Several researchers asked wether this bound could be improved to (1 - ε)Ω(n/s); this question is usually referred to as the strong parallel repetition problem. We show that the answer for this question is negative. More precisely, we consider the odd cycle game of size m; a two-prover game with value 1 - 1/2m. We show that the value of the odd cycle game repeated in parallel n times is at least 1 - (1/m) · O(√n). This implies that for large enough n (say, n ≥ Ω(m2)), the value of the odd cycle game repeated in parallel n times is at least (1 - 1/4m2)O(n). Thus: 1. For parallel repetition of general games: the bounds of (1 - εc)Ω(n/s) given in [13, 7] are of the right form, up to determining the exact value of the constant c ≥ 2. 2. For parallel repetition of XOR games, unique games and projection games: the bounds of (1 - ε2)Ω(n) given in [5] (for XOR games) and in [12] (for unique and projection games) are tight. 3. For parallel repetition of the odd cycle game: the bound of 1- (1/m) · Ω̃(√n) given in [5] is almost tight. A major motivation for the recent interest in the strong parallel repetition problem is that a strong parallel repetition theorem would have implied that the unique game conjecture is equivalent to the NP hardness of distinguishing between instances of Max-Cut that are at least 1 - ε2 satisfiable from instances that are at most 1 - (2/π) · ε satisfiable. Our results suggest that this cannot be proved just by improving the known bounds on parallel repetition.
UR - http://www.scopus.com/inward/record.url?scp=58049126989&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=58049126989&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2008.49
DO - 10.1109/FOCS.2008.49
M3 - Conference contribution
AN - SCOPUS:58049126989
SN - 9780769534367
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 369
EP - 373
BT - Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008
T2 - 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008
Y2 - 25 October 2008 through 28 October 2008
ER -