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. (C) 2000 Elsevier Science Inc. All rights reserved.
|Autori:||Codenotti B; Del Corso G; Manzini G|
|Titolo:||Matrix rank and communication complexity|
|Anno del prodotto:||2000|
|Digital Object Identifier (DOI):||10.1016/S0024-3795(99)00226-8|
|Appare nelle tipologie:||1.1 Articolo in rivista|