Matrix rank and communication complexity
type: Item
instance of: scholarly article
title: Matrix rank and communication complexity
zbMATH Open document ID: 0952.15003
DOI: 10.1016/S0024-3795(99)00226-8
author: Gianna M. Del Corso
author: Giovanni Manzini
author: Bruno Codenotti
published in: Linear Algebra and its Applications
publication date: 2001-01-03T00:00:00Z
review text: 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.
reviewed by: M. Ladra
Mathematics Subject Classification ID: 15A03
Mathematics Subject Classification ID: 94A05
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 1420041
zbMATH Keywords: matrix rank
zbMATH Keywords: communication complexity
zbMATH Keywords: chromatic number
zbMATH Keywords: adjacency matrix
zbMATH Keywords: low-rank matrices
zbMATH Keywords: protocol
describes a project that uses: GRAFFITI
MaRDI profile type: Publication
cites work: A counterexample to the rank-coloring conjecture
cites work: Algebraic techniques in communication complexity
cites work: On conjectures of Graffiti
cites work: The Probabilistic Communication Complexity of Set Intersection
cites work: Rank and chromatic number of a graph
cites work: The rank and size of graphs
cites work: A Bound for the Chromatic Number of a Graph
cites work: Communication in bounded depth circuits
cites work: Modified ranks of tensors and the size of circuits
cites work: Boolean Circuits, Tensor Ranks, and Communication Complexity
cites work: Q4864428
cites work: The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear
Wikidata QID: Q127088677
Recommended article: The communication complexity of several problems in matrix computation
Recommended article: On rank vs. communication complexity
Recommended article: Communication complexity of matrix computation over finite fields
Recommended article: Still another rank determination of set intersection matrices with an application in communication complexity
Recommended article: An Additive Combinatorics Approach Relating Rank to Communication Complexity
Recommended article: Upper bounds on communication in terms of approximate rank
Recommended article: On the Complexity of Matrix Rank and Rigidity
Recommended article: On the complexity of matrix rank and rigidity
Recommended article: Complexity of matrix problems
Recommended article: Some structural properties of low-rank matrices related to computational complexity
description: scientific article; zbMATH DE number 1420041