On the Role of Shared Randomness in Simultaneous Communication
On the Role of Shared Randomness in Simultaneous Communication
复制标题
论共享随机性在同步通信中的作用
DOI：
10.1007/978-3-662-43948-7_13
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Tsuyoshi Ito
中科院分区：
文献类型：
--
作者：
Mohammad Bavarian;Dmitry Gavinsky;Tsuyoshi Ito
两党希望执行某些分布式计算任务，并可以访问相关的随机位来源。它允许各方以相关的方式行事，这很有用。但是，如果共享随机性不是完美的，会发生什么？在这项工作中，我们启动了交流复杂性中共享随机性不同来源的力量的研究。这是在交流复杂性的同时消息传递（SMP）模型的设置中完成的，这是研究共享随机性资源的最合适模型之一。为了表征共享随机性的各种来源的力量，我们引入了来源质量的衡量标准 - 我们称其为碰撞复杂性。我们的结果表明，碰撞复杂性紧密地表征了SMP模型中A（共享）随机性资源的功能。
我们的独立兴趣是我们的证明，即使是共享随机性的最弱来源也可以大大增加SMP的力量：相等函数几乎可以通过几乎任何非平凡的共享随机性来非常有效地解决。
Two parties wish to carry out certain distributed computational tasks, and they are given access to a source of correlated random bits. It allows the parties to act in a correlated manner, which can be quite useful. But what happens if the shared randomness is not perfect? In this work, we initiate the study of the power of different sources of shared randomness in communication complexity. This is done in the setting of simultaneous message passing (SMP) model of communication complexity, which is one of the most suitable models for studying the resource of shared randomness. Toward characterising the power of various sources of shared randomness, we introduce a measure for the quality of a source - we call it collision complexity. Our results show that the collision complexity tightly characterises the power of a (shared) randomness resource in the SMP model.
Of independent interest is our demonstration that even the weakest sources of shared randomness can in some cases increase the power of SMP substantially: the equality function can be solved very efficiently with virtually any nontrivial shared randomness.