Communication Complexity and Quasi Randomness
Communication Complexity and Quasi Randomness
复制标题
通信复杂性和准随机性
DOI：
10.1137/0406009
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
P. Tetali
中科院分区：
文献类型：
--
作者：
F. C. Graham;P. Tetali
多方通信复杂度涉及必须在多个参与者之间交换以协作计算布尔函数$f（x_1，\ldots，x_k）$的最少比特数，而每个参与者对于某个固定的$t < k$最多知道t个输入。研究了多方通信复杂性与超图的各种性质之间的关系。随机超图满足这些性质中的许多性质，并且可以用拟随机性的框架进行分类。也就是说，超图的许多不同的属性被证明是相互等价的，而且，各种等价类形成一个自然的层次结构。本文证明了多方通信复杂性问题等价于超图的某些性质，从而建立了超图或布尔函数的大量组合和计算方面之间的联系。
The multiparty communication complexity concerns the least number of bits that must be exchanged among a number of players to collaboratively compute a Boolean function $f ( x_1 , \ldots ,x_k )$, while each player knows at most t inputs for some fixed $t < k$. The relation of the multiparty communication complexity to various hypergraph properties is investigated. Many of these properties are satisfied by random hypergraphs and can be classified by the framework of quasi randomness. Namely, many disparate properties of hypergraphs are shown to be mutually equivalent, and, furthermore, various equivalence classes form a natural hierarchy. In this paper, it is proved that the multiparty communication complexity problems are equivalent to certain hypergraph properties and thereby establish the connections among a large number of combinatorial and computational aspects of hypergraphs or Boolean functions.