Certifying Equality With Limited Interaction
Certifying Equality With Limited Interaction
复制标题
通过有限的互动来证明平等
DOI：
10.1007/s00453-016-0163-6
复制
发表时间：
2016
期刊：
影响因子：
1.1
通讯作者：
Yaroslavtsev, Grigory
中科院分区：
文献类型：
--
作者：
Brody, Joshua;Chakrabarti, Amit;Kondapally, Ranganath;Woodruff, David P.;Yaroslavtsev, Grigory
平等问题通常是人们第一次遇到通信复杂性，也是该领域最基本的问题之一。尽管其确定性和随机通信的复杂性在几十年前就已得到解决，但通过关注三个微妙的方面，我们发现了一些关于该问题的新内容。首先是考虑使用有限交互（即有限数量的通信轮次）并且其错误概率为零或接近零的协议的预期通信成本（在最坏情况输入下）。第二个是将假阴性错误率与假阳性错误率分开处理。第三是考虑此类协议的信息成本。我们获得了渐近最优的轮数与成本权衡：预期的通信复杂性和信息复杂性都随着轮数的变化而变化，klogs 也随之增加。即使当假阴性率接近 1 时，这些界限仍然成立。对于零错误通信成本的情况，我们获得基本上匹配的界限，直到一个微小的加性常数。我们还提供一些应用程序。作为我们的信息成本界限的应用，我们获得了交叉问题的新的有界轮随机下界，其中有两个持有子集的玩家。在许多现实场景中，SandTa 的大小明显小于 n，因此我们施加约束。我们研究各方需要通信的最小位数，以便使用轮次计算整个交集。我们证明任何一轮协议都有信息成本（以及通信成本）位。我们还给出了一个 O(r) 轮协议实现位，它原谅了具有 O(k) 位通信的协议。这与其他基本问题形成对比，例如计算并集或对称差，任何轮数都需要通信位。
Theequalityproblem is usually one’s first encounter with communication complexity and is one of the most fundamental problems in the field. Although its deterministic and randomized communication complexity were settled decades ago, we find several new things to say about the problem by focusing on three subtle aspects. The first is to consider theexpectedcommunication cost (at a worst-case input) for a protocol that uses limited interaction—i.e., a bounded number of rounds of communication—and whose error probability is zero or close to it. The second is to treat thefalse negativeerror rate separately from thefalse positiveerror rate. The third is to consider theinformation costof such protocols. We obtain asymptotically optimal rounds-versus-cost tradeoffs forequality: both expected communication complexity and information complexity scale as, whereris the number of rounds and, withklogs. These bounds hold even when the false negative rate approaches 1. For the case of zero-error communication cost, we obtain essentially matching bounds, up to a tiny additive constant. We also provide some applications. As an application of our information cost bounds, we obtain new bounded-round randomized lower bounds for theIntersectionproblem, in which there are two players who hold subsets. In many realistic scenarios, the sizes ofSandTare significantly smaller thann, so we impose the constraint that. We study the minimum number of bits the parties need to communicate in order to compute the entire intersection set, usingrrounds. We show that anyr-round protocol has information cost (and thus communication cost)bits. We also give anO(r)-round protocol achievingbits, which forgives a protocol withO(k) bits of communication. This is in contrast to other basic problems such as computing the union or symmetric difference, for whichbits of communication is required for any number of rounds.
登录
查看更多内容
量子和近似隐私
影响因子：
0.5
作者：
H. Klauck
通讯作者：
H. Klauck
两方有界轮公币通信复杂性的直积定理
影响因子：
1.1
作者：
Rahul Jain;A. Pereszlényi;Penghui Yao
通讯作者：
Penghui Yao
DOI：
10.1007/978-3-642-39206-1_20
发表时间：
2013
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
M. Braverman;Anup Rao;Omri Weinstein;A. Yehudayoff
通讯作者：
A. Yehudayoff
通过信息论的稀疏和不平衡集合不相交
DOI：
10.1007/978-3-642-32512-0_44
发表时间：
2012
期刊：
2013 IEEE 54th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Anirban Dasgupta;Ravi Kumar;D. Sivakumar
通讯作者：
D. Sivakumar
摊销通信复杂性（初步版本）
DOI：
10.1109/sfcs.1991.185374
发表时间：
1991
期刊：
Commun. ACM
影响因子：
--
作者：
Tomás Feder;Eyal Kushilevitz;M. Naor
通讯作者：
M. Naor