Title :
On rank vs. communication complexity
Author :
Nisan, Noam ; Wigderson, Avi
Author_Institution :
Inst. of Comput. Sci., Hebrew Univ., Jerusalem, Israel
Abstract :
This paper concerns the open problem of Lovasz and Saks (1988) 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
Keywords :
Boolean functions; communication complexity; matrix algebra; Boolean function; associated function; associated matrix; communication complexity; deterministic communication complexity; matrix; rank; Boolean functions; Complexity theory; Computer science; Protocols;
Conference_Titel :
Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on
Conference_Location :
Santa Fe, NM
Print_ISBN :
0-8186-6580-7
DOI :
10.1109/SFCS.1994.365711
