Direct product results and the GCD problem, in old and new communication models
Direct product results and the GCD problem, in old and new communication models
复制标题
新旧通信模型中的直接乘积结果和 GCD 问题
DOI：
10.1145/258533.258620
复制
发表时间：
1997
期刊：
影响因子：
1.1
通讯作者：
A. Wigderson
中科院分区：
文献类型：
--
作者：
Itzhak Parnafes;R. Raz;A. Wigderson
本文包含有关通信复杂性模型和2个磁带游戏模型的几个结果，这些结果基于两个模型之间的相互作用：1。我们展示了如何提高[RA]的平行重复定理的指数下降速率验证者谓词的通信复杂性的术语。 2。我们应用了2个2个游戏游戏的改进的并行重复定理，这是第一次获得通信复杂性的直接产品定理。第二个推导使用两个模型的共同概括，这是独立有趣的。我们通过考虑$ GCD $问题来启动其功率的研究，以及它的一些变化，这些变化在新模型和经典通信复杂性模型之间表现出功率差距。该差距部分基于以下上限：给定$ n $ bit Inputs $ x $和$ y $分别向爱丽丝和鲍勃，它们可以仅使用$ o（n = log n n = log n ）$通讯位：1。确定$ gcd（x; y）= 1 $和$ b $（由鲍勃），满足$ a _ x + b _ y = 1 $。观察到第二任任务中的输出总体上是$（n）$。对这两个问题的通信复杂性（在几种模型和模式中）进行了完整分析。
This paper contains several results regarding the communication complexity model and the 2-prover games model, which are based on interaction between the two models: 1. We show how to improve the rate of exponential decrease in the parallel repetition theorem of [Ra] in terms of the communication complexity of the verifier's predicate. 2. We apply the improved parallel repetition theorem of 2-prover games to derive, for the first time, a direct product theorem for communication complexity. The second derivation uses a common generalization of the two models, which is independently interesting. We initiate a study of its power by considering the $GCD$ problem, and some variations of it, which exhibit a power gap between the new model and the classical communication complexity model. This gap is partly based on the following upper bounds: Given $n$-bit inputs $x$ and $y$ to Alice and Bob respectively, they can achieve the tasks below with very high probability using only $O(n= log n)$ communication bits: 1. Decide if $GCD(x; y) = 1$ and $b$ (by Bob), satisfying $a _ x + b _ y = 1$. Observe that the outputs in the second task are in general of length $(n)$. A complete analysis of the communication complexity of these two problems (in several models and modes) is given.