Linear algebraic methods in communication complexity

AbstractThe notion of communication complexity seeks to capture the amount of communication between different parties that is required to find the output of a Boolean function when each party is provided with only part of the input. Different variants of the model governing the rules of this communication lead to different connections with problems in combinatorial linear algebra. In particular, problems arise in this context that concern the rank of a (0,1)-matrix and the minimum rank of a matrix meeting a given combinatorial description. This paper surveys these connections