Matrix rank and communication complexity Original Research Article

The rank of a matrix seems to play a role in the context of communication complexity, a framework developed to analyze basic communication requirements of computational problems. We present some issues and open problems arising in this area, and put forward a number of research subjects in linear algebra, whose investigation would shed new lights into the intriguing relationship between communication complexity and matrix rank. We also mention the related problem of the accuracy of bounds on the chromatic number of a graph given in terms of the rank of its adjacency matrix.