To refer to this page use:

`http://arks.princeton.edu/ark:/88435/pr1rc0g`

Abstract: | We 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− )-probability by communicating at most bits of information, then one can win n copies with probability at least 2 −O( n) . This gives an intuitive explanation why Raz’s counter-example to strong parallel repetition [16] (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 − ) n, then one can win one copy with at least (1 − O( ))-probability by communicating O( ) 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. |

Publication Date: | 2018 |

Citation: | Braverman, Mark, and Young Kun Ko. "Information value of two-prover games." In 9th Innovations in Theoretical Computer Science Conference (ITCS) 94 (2018): pp. 12:1-12:15. doi:10.4230/LIPIcs.ITCS.2018.12 |

DOI: | 10.4230/LIPIcs.ITCS.2018.12 |

ISSN: | 1868-8969 |

Pages: | 12:1 - 12:15 |

Type of Material: | Conference Article |

Series/Report no.: | Leibniz International Proceedings in Informatics (LIPIcs); |

Journal/Proceeding Title: | 9th Innovations in Theoretical Computer Science Conference (ITCS) |

Version: | Final published version. This is an open access article. |

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.