Rounding parallel repetitions of Unique Games
with Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev. FOCS 2008.
abstract
We show a connection between the semidefinite relaxation of unique games and their behavior under parallel repetition. Specifically, denoting by the value of a two-prover unique game , and by the value of a natural semidefinite program to approximate , we prove that for every , if , then Here, denotes the -fold parallel repetition of , and , where denotes the alphabet size of the game. For the special case where is an XOR game (i.e., ), we obtain the same bound but with as an absolute constant. Our bounds on are optimal up to a factor of .
For games with a significant gap between the quantities and , our result implies that may be much larger than , giving a counterexample to the strong parallel repetition conjecture. In a recent breakthrough, Raz (FOCS '08) has shown such an example using the max-cut game on odd cycles. Our results are based on a generalization of his techniques.
keywords
- Unique Games Conjecture
- semidefinite programming