Some Improved Bounds on Communication Complexity via New Decomposition of Cliques
Some Improved Bounds on Communication Complexity via New Decomposition of Cliques
复制标题
通过新的派系分解，改善了通信复杂性的界限
DOI：
10.1016/j.dam.2013.09.015
复制
发表时间：
2014
影响因子：
1.1
通讯作者：
Kazuyuki Amano
中科院分区：
文献类型：
--
作者：
T. Horiyama;W. Shoji;Kazuyuki Amano
完全图Kn在n个顶点上的有序双体划分是一个双体(即完全二部图)的集合，使得(I)Kn的每条边被集合中至少一个且至多两个双体覆盖，以及(Ii)如果边e被两个双体覆盖，则e的每个端点在其中一个双体中处于第一类，在另一个双体中处于第二类。我们在本文中证明了这样一个集合的最小大小是O(n2/3)。这在与通信复杂性相关的两个问题上给出了新的结果。也就是说，(I)愚弄集的大小与0/1-矩阵的秩间的一种新的分离，以及(Ii)团与独立集问题的不确定性通信复杂性的一个改进的下界。
An ordered biclique partition of the complete graph K n on n vertices is a collection of bicliques (ie, complete bipartite graphs) such that (i) every edge of K n is covered by at least one and at most two bicliques in the collection, and (ii) if an edge e is covered by two bicliques then each endpoint of e is in the first class in one of these bicliques and in the second class in the other one. We show in this note that the minimum size of such a collection is O (n 2/3). This gives new results on two problems related to communication complexity. Namely,(i) a new separation between the size of a fooling set and the rank of a 0/1-matrix, and (ii) an improved lower bound on the nondeterministic communication complexity of the clique vs. independent set problem are given.