Public vs. private coin flips in one round communication games (extended abstract)
Public vs. private coin flips in one round communication games (extended abstract)
复制标题
一轮通信游戏中的公共与私人掷硬币（扩展摘要）
DOI：
10.1145/237814.238004
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
M. Szegedy
中科院分区：
文献类型：
--
作者：
I. Newman;M. Szegedy
我们研究了l轮双方通信复杂性博弈，其中使用了私有随机比特。我们观察到，存在良好的协议，这样的游戏是有关的一个概念，近似的矩阵，代表了一定的低秩矩阵的功能。这就产生了一个新的秩概念，类似于l轮通信复杂度的正秩。我们证明了在这个意义上单位矩阵不可由低秩矩阵逼近。作为推论，我们证明了等式函数的任何随机化协议都需要f 2（@ l轮，私有比特模型中的复杂度，回答了Yao [8]提出的一个公开问题。一个推论是对以下图论问题的回答：假设一个n个顶点的图有一组N = N（n）团，因此对于这组的每两个不同的团，它们之间的边数至多是它们的大小的乘积的0.1。N能有多大？我们证明了N = n（tlogn）是正确的数量级。
We study l-round two parties communication complexity games, where private random bits are used. We observe that the existence of good protocols for such games is related to a notion of approximating the matrix that represents the function by a certain low rank matrix. This gives rise to a new notion of rank, analogous of positive rank for l-round communication complexity. We prove that the identity matrix is non approximable by low rank matrices in this sense. As a corollary we prove that any randomized protocol for the equality function requires f2(@ complexity in the l-round, private bits model, answering an open question raised by Yao [8]. A corollary is an answer to the following graph theoretic question: Assume a graph on n vertices has a set of N = N(n) cliques and so that for each two different cliques of this set, the number of edges between them is at most 0.1 of the product of their sizes. How large can N be ? We show that N = n“tlogn) is the right order of magnitude.