TY - GEN

T1 - Public vs. private coin flips in one round communication games

AU - Newman, Ilan

AU - Szegedy, Mario

N1 - Publisher Copyright:
© 1996 ACM.

PY - 1996/7/1

Y1 - 1996/7/1

N2 - We study 1-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 1-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 Ω(√n) complexity in the 1-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θ(log n) is the right of magnitude.

AB - We study 1-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 1-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 Ω(√n) complexity in the 1-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θ(log n) is the right of magnitude.

UR - http://www.scopus.com/inward/record.url?scp=0029706950&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0029706950&partnerID=8YFLogxK

U2 - 10.1145/237814.238004

DO - 10.1145/237814.238004

M3 - Conference contribution

AN - SCOPUS:0029706950

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 561

EP - 570

BT - Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996

PB - Association for Computing Machinery

T2 - 28th Annual ACM Symposium on Theory of Computing, STOC 1996

Y2 - 22 May 1996 through 24 May 1996

ER -