文章基本信息

标题：Parallel Repetition of Two-Prover One-Round Games: An Exposition
本地全文：下载
作者：Suguru TAMAKI
期刊名称：Interdisciplinary Information Sciences
印刷版ISSN：1340-9050
电子版ISSN：1347-6157
出版年度：2015
卷号：21
期号：4
页码：289-306
DOI：10.4036/iis.2015.L.01
出版社：The Editorial Committee of the Interdisciplinary Information Sciences
摘要：A two-prover one-round game is a fundamental combinatorial optimization problem arising from such areas as interactive proof systems, hardness of approximation, cryptography and quantum mechanics. The parallel repetition theorem states that for any two-prover one-round game with value smaller than 1, k -fold parallel repetition reduces the value of the game exponentially in k . The theorem was originally proved by Raz (SICOMP 1998) and later simplified and improved by Holenstein (Theory of Computing 2009) and Rao (SICOMP 2011). All the known proofs are based on information theoretic arguments. Very recently, Dinur and Steurer (STOC 2014) obtained a new proof of the parallel repetition theorem based on a matrix analysis argument. In this paper, we describe a special case of Dinur and Steurer's proof. We also describe an application of the parallel repetition theorem to inapproximability results of two-prover one-round games. Our presentation is almost self-contained in the sense that we only assume the PCP theorem. To do so, we also present proofs for the necessary results related to algebraic graph theory and hardness of approximation.
关键词：interactive proof system;hardness of approximation;spectral graph theory;matrix analysis;label cover