Name
Abstract | ||
|---|---|---|
We show a connection between the semidefinite relaxation of unique games and their behavior under parallel repetition. Specifically,denoting by val(G) the value of a two-prover unique game G, andby sdpval(G) the value of a natural semidefinite program to approximate val(G), we prove that for every l epsi N, if sdpval(G) ges 1-delta, then val(Gl) ges 1-radicsldelta. Here, Gl denotes the l-fold parallel repetition of G, and s=O(log(k/delta)), where k denotes the alphabet size of the game. For the special case where G is an XOR game (i.e., k=2), we obtain the same bound but with s as an absolute constant. Our bounds on s are optimal up to a factor of O(log(1/delta)). For games with a significant gap between the quantities val(G) and sdpval(G), our result implies that val(Gl) may be much larger than val(G)l, 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 oddcycles. Our results are based on a generalization of his techniques. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1109/FOCS.2008.55 | FOCS |
Keywords | Field | DocType |
alphabet size,natural semidefinite program toapproximate,foldparallel repetition,parallel repetition,mathematical programming,semidefinite relaxation,mathbb n,parallel repetitions,computational complexity,game theory,hellinger distance,semidefinite programming,unique games,two-prover unique game,xor game,max-cut game,natural semidefinite program,correlated sampling,strongparallel repetition conjecture,games,probability,computer science,programming | Discrete mathematics,Distance measurement,Combinatorics,Rounding,Game theory,Counterexample,Conjecture,Mathematics,Semidefinite programming,Alphabet,Computational complexity theory | Conference |
ISSN | ISBN | Citations |
0272-5428 | 978-0-7695-3436-7 | 23 |
PageRank | References | Authors |
1.26 | 16 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Boaz Barak | 1 | 2563 | 127.61 |
| Moritz Hardt | 2 | 1460 | 82.08 |
| Ishay Haviv | 3 | 91 | 9.86 |
| Anup Rao | 4 | 581 | 32.80 |
| Oded Regev | 5 | 2322 | 133.33 |
| David Steurer | 6 | 934 | 44.91 |