On Rank vs. Communication Complexity

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. >

Authors

• Noam Nisan
• Avi Wigderson

Keywords

• Complexity theory
• Boolean functions
• Computer science
• Protocols
• Complex Communication
• Boolean Function
• Lower Bound
• Conjecture
• Proof Of Theorem
• Matrix M
• Submatrix
• Size Of The Intersection
• L Matrix
• Boolean Matrix