Lower Bounds on the Multiparty Communication Complexity
Lower Bounds on the Multiparty Communication Complexity
复制标题
多方通信复杂性的下限
DOI：
10.1006/jcss.1997.1547
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
J. Rolim
中科院分区：
文献类型：
--
作者：
P. Duris;J. Rolim
我们推导出一种通用技术，用于获得布尔函数多方通信复杂性的下限。我们将基于 Yao 引入的交叉序列论证的两方方法扩展到多方通信模型。我们使用我们的技术来导出一些简单布尔函数的最佳下限和上限。多方模型的下限一直是一个挑战（D. Dolev 和 T. Feder，在“Proceedings，第 30 届 IEEE FOCS，1989”，第 428?433 页），其中仅导出了计算布尔函数 f(x1, ?, xn) 的确定性算法所交换的位数的上限，即阶数 (k0C0)(k1C1)2，达到对数因子，其中k1和C1是在f的非确定性算法中访问的处理器和交换的位的数量，k0和C0是互补函数1?f的类似参数。我们证明了C0?n(1+2C1)和D?n(1+2C1)，其中Dis是由确定性算法计算f所交换的位数。我们还研究了受限多方通信模型的威力，在该模型中，协调器最多可以向每一方发送一条消息。
We derive a general technique for obtaining lower bounds on the multiparty communication complexity of boolean functions. We extend the two-party method based on a crossing sequence argument introduced by Yao to the multiparty communication model. We use our technique to derive optimal lower and upper bounds of some simple boolean functions. Lower bounds for the multiparty model have been a challenge since (D. Dolev and T. Feder,in“Proceedings, 30th IEEE FOCS, 1989,” pp. 428?433), where only an upper bound on the number of bits exchanged by a deterministic algorithm computing a boolean functionf(x1, ?, xn) was derived, namely of the order (k0C0)(k1C1)2, up to logarithmic factors, wherek1andC1are the number of processors accessed and the bits exchanged in a nondeterministic algorithm forf, andk0andC0are the analogous parameters for the complementary function 1?f. We show thatC0?n(1+2C1) andD?n(1+2C1), whereDis the number of bits exchanged by a deterministic algorithm computingf. We also investigate the power of a restricted multiparty communication model in which the coordinator is allowed to send at most one message to each party.