首页    期刊浏览 2024年12月02日 星期一
登录注册

文章基本信息

  • 标题:Information Value of Two-Prover Games
  • 本地全文:下载
  • 作者:Mark Braverman ; Young Kun Ko
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2017
  • 卷号:2017
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    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 [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 − ) 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.

  • 关键词:odd cycle game ; Parallel Repetition ; Two-prover games
国家哲学社会科学文献中心版权所有