Parallel Repetition of the Odd Cycle Game

Abstract

Higher powers of the Odd Cycle Game has been the focus of recent investigations [3,4]. In [4] it was shown that if we repeat the game d times in parallel, the winning probability is upper bounded by $1-\Omega({\sqrt{d}\over n\sqrt{\log d}})$, when d ≤ n ²logn. We

• 1 Determine the exact value of the square of the game;

• 1 Show that if Alice and Bob are allowed to communicate a few bits they have a strategy with greatly increased winning probability;

• 1 Develop a new metric conjectured to give the precise value of the game up-to second order precision in 1/n for constant d.

• 1 Show an 1 − Ω(d/nlogn) upper bound for d ≤ nlogn if one player uses a “symmetric” strategy.