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.
Matrix rank and communication complexity
DEL CORSO, GIANNA MARIA;Manzini G.
2000-01-01
Abstract
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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
