On rank vs. communication complexity
Noam Nisan, Avi Wigderson · 2002
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.>