ECCC-Report TR17-182https://eccc.weizmann.ac.il/report/2017/182Comments and Revisions published for TR17-182en-usTue, 28 Nov 2017 07:53:38 +0200
Paper TR17-182
| Information Value of Two-Prover Games |
Mark Braverman,
Young Kun Ko
https://eccc.weizmann.ac.il/report/2017/182We introduce a generalization of the standard framework for studying the difficulty of two-prover games. Specifically, we study the model where Alice and Bob are allowed to communicate (with information constraints) --- in contrast to the usual two-prover game where they are not allowed to communicate after receiving their respective input. We study the trade-off between the information cost of the protocol and the achieved value of the game after the protocol. In particular, we show the connection of this trade-off and the amortized behavior of the game (i.e. repeated value of the game). We show that if one can win the game with at least $(1 - \epsilon)$-probability by communicating at most $\epsilon$ bits of information, then one can win $n$ copies with probability at least $2^{-O(\epsilon n)}$. This gives an intuitive explanation why Raz's counter-example to strong parallel repetition [Raz08] (the odd cycle game) is a counter-example to strong parallel repetition --- one can win the odd-cycle game on a cycle of length $m$ by communicating $O(m^{-2})$-bits where $m$ is the number of vertices.
Conversely, for projection games, we show that if one can win $n$ copies with probability larger than $(1-\epsilon)^n$, then one can win one copy with at least $(1 - O(\epsilon))$-probability by communicating $O(\epsilon)$ bits of information. By showing the equivalence between information value and amortized value, we give an alternative direction for further works in studying amortized behavior of the two-prover games.
The main technical tool is the ``Chi-Squared Lemma'' which bounds the information cost of the protocol in terms of Chi-Squared distance,
instead of usual divergence. This avoids the square loss from using Pinsker's Inequality.Tue, 28 Nov 2017 07:53:38 +0200https://eccc.weizmann.ac.il/report/2017/182