Name
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 - Ω(√d/n√log d), when d ≤ n2 log n. We 1. Determine the exact value of the square of the game; 2. Show that if Alice and Bob are allowed to communicate a few bits they have a strategy with greatly increased winning probability; 3. Develop a new metric conjectured to give the precise value of the game up-to second order precision in 1/n for constant d. 4. Show an 1 - Ω(d/n log n) upper bound for d ≤ n log n if one player uses a "symmetric" strategy. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-78773-0_58 | LATIN |
Keywords | Field | DocType |
odd cycle game,recent investigation,higher power,winning probability,n log n,order precision,precise value,parallel repetition,exact value,n2 log n,second order,upper bound | Discrete mathematics,Combinatorics,Alice and Bob,Upper and lower bounds,Time complexity,Mathematics,Bounded function | Conference |
Volume | ISSN | ISBN |
4957 | 0302-9743 | 3-540-78772-0 |
Citations | PageRank | References |
3 | 0.55 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kooshiar Azimian | 1 | 3 | 2.92 |
| Mario Szegedy | 2 | 3358 | 325.80 |