Probabilistic Communication Complexity
Probabilistic Communication Complexity
复制标题
DOI：
10.1016/0022-0000(86)90046-2
复制
发表时间：
1986-08
期刊：
影响因子：
--
通讯作者：
R. Paturi;Janos Simon
中科院分区：
文献类型：
--
作者：
R. Paturi;Janos Simon
通信是许多分布式计算的瓶颈。在VLSI中，通信限制规定了芯片性能的下限。双处理器信息传输模型衡量计算功能的通信需求。我们研究了该模型的无界误差概率形式。由于它对正确输出的概念较弱，我们认为该模型测量了函数的“内在”通信复杂性。通过超平面的排列和矩阵的逼近，我们给出了无界误差通信复杂性的精确刻画。这些刻画建立了与组合几何中某些经典问题的联系，这些问题涉及d维实空间中的点的构形。利用这些刻画，我们得到了通信复杂性的一些上界和下界。我们得到的函数的上界--汉明距离的等价性和验证性--比确定性、不确定性和有界误差概率模型中的相应上界要好得多。我们还展示了一个具有logn复杂性的函数。我们给出了一个计数论据，证明了大多数函数都具有线性复杂性。进一步，我们应用通信复杂度的对数下界得到了1带无界误差概率图灵机时间的Ω(Nlogn)界。我们相信这是此类机器的第一个非平凡下界。
Communication is a bottleneck in many distributed computations. In VLSI, communication constraints dictate lower bounds on the performance of chips. The two-processor information transfer model measures the communication requirements to compute functions. We study the unbounded error probabilistic version of this model. Because of its weak notion of correct output, we believe that this model measures the “intrinsic” communication complexity of functions. We present exact characterizations of the unbounded error communication complexity in terms of arrangements of hyperplanes and approximations of matrices. These characterizations establish the connection with certain classical problems in combinatorial geometry which are concerned with the configurations of points in d-dimensional real space. With the help of these characterizations, we obtain some upper and lower bounds on communication complexity. The upper bounds which we obtained for the functions—equality and verification of Hamming distance—are considerably better than their counterparts in the deterministic, the nondeterministic, and the bounded error probabilistic models. We also exhibit a function which has log n complexity. We present a counting argument to show that most functions have linear complexity. Further, we apply the logarithmic lower bound on communication complexity to obtain an Ω (n log n) bound on the time of 1-tape unbounded error probabilistic Turing machines. We believe that this is the first nontrivial lower bound obtained for such machines.