Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR94-001 | 12th December 1994 00:00

On Rank vs. Communication Complexity

RSS-Feed




TR94-001
Authors: Noam Nisan, Avi Wigderson
Publication: 12th December 1994 00:00
Downloads: 3629
Keywords: 


Abstract:

This paper concerns the open problem of Lovasz and
Saks regarding the relationship between the communication complexity
of a boolean function and the rank of the associated matrix.
We first give an example exhibiting the largest gap known. We then
prove two related theorems.



ISSN 1433-8092 | Imprint