Braverman, Mark ;
Ko, Young Kun
Information Value of TwoProver Games
Abstract
We introduce a generalization of the standard framework for studying the difficulty of twoprover games. Specifically, we study the model where Alice and Bob are allowed to communicate (with information constraints)  in contrast to the usual twoprover game where they are not allowed to communicate after receiving their respective input. We study the tradeoff 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 tradeoff 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 counterexample to strong parallel repetition [Raz2008] (the odd cycle game) is a counterexample to strong parallel repetition  one can win the oddcycle 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 twoprover games.
The main technical tool is the "ChiSquared Lemma" which bounds the information cost of the protocol in terms of ChiSquared distance,
instead of usual divergence. This avoids the square loss from using Pinsker's Inequality.
BibTeX  Entry
@InProceedings{braverman_et_al:LIPIcs:2018:8346,
author = {Mark Braverman and Young Kun Ko},
title = {{Information Value of TwoProver Games}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {12:112:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770606},
ISSN = {18688969},
year = {2018},
volume = {94},
editor = {Anna R. Karlin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8346},
URN = {urn:nbn:de:0030drops83466},
doi = {10.4230/LIPIcs.ITCS.2018.12},
annote = {Keywords: Two Prover Game, Parallel Repetition, OddCycle Game, Amortized Value of the Game}
}
12.01.2018
Keywords: 

Two Prover Game, Parallel Repetition, OddCycle Game, Amortized Value of the Game 
Seminar: 

9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Issue date: 

2018 
Date of publication: 

12.01.2018 