Matrix rank and communication complexity (Q1970502)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Matrix rank and communication complexity |
scientific article |
Statements
Matrix rank and communication complexity (English)
0 references
3 January 2001
0 references
The central notion in communication is a protocol, which is essentially a set of rules specifying the order and the meaning of the messages sent. A protocol can be analyzed in terms of ranks of the submatrices detected as the rounds proceed. The authors present some results and open problems in the area of communication complexity and on the chromatic number of a graph in terms of the rank of a matrix.
0 references
matrix rank
0 references
communication complexity
0 references
chromatic number
0 references
adjacency matrix
0 references
low-rank matrices
0 references
protocol
0 references
