文章基本信息

标题：The Parallel Repetition Conjecture for Trees is True
本地全文：下载
作者：Oleg Verbitsky
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1995
卷号：1995
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The parallel repetition conjecture (PRC) of Feige and Lovasz says that the error probability of a two prover one round interactive protocol repeated n times in parallel is exponentially small in n. We show that the PRC is true in the case when the bipartite graph of dependence between queries to provers is a tree. Previously this was known only in the case of complete bipartite graphs (i.e. when the queries to provers are independent). We suggest also the combinatorial characterization of method that was used to obtain most results towards the PRC and discuss some related combinatorial problems.
关键词：extremal finite set theory Warning: DO NOT SEND LONG UNAUTHORIZED FILES TO THE ABOVE ADDRESS, games of incomplete information, interactive proof system, Ramsey theory