首页    期刊浏览 2024年11月30日 星期六
登录注册

文章基本信息

  • 标题:A New Proof of Nonsignalling Multiprover Parallel Repetition Theorem
  • 本地全文:下载
  • 作者:Himanshu Tyagi ; Shun Watanabe
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-6
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We present an information theoretic proof of the nonsignalling multiprover parallel repetition theorem, a recent extension of its two-prover variant that underlies many hardness of approximation results. The original proofs used de Finetti type decomposition for strategies. We present a new proof that is based on a technique we introduced recently for proving strong converse results in multiuser information theory and entails a change of measure after replacing hard information constraints with soft ones.

国家哲学社会科学文献中心版权所有