Matrix rank and communication complexity

DOI10.1016/S0024-3795(99)00226-8zbMath0952.15003WikidataQ127088677 ScholiaQ127088677MaRDI QIDQ1970502

Giovanni Manzini, Gianna M. Del Corso, Bruno Codenotti

Publication date: 3 January 2001

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

zbMATH Keywords

adjacency matrixchromatic numberprotocolcommunication complexitymatrix ranklow-rank matrices

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vector spaces, linear dependence, rank, lineability (15A03) Communication theory (94A05)

Related Items (3)

Linear algebraic methods in communication complexity ⋮ The minimum semidefinite rank of a triangle-free graph ⋮ Extremal problems under dimension constraints.

Uses Software

• GRAFFITI

Cites Work

• Unnamed Item
• On conjectures of Graffiti
• The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear
• Communication in bounded depth circuits
• Algebraic techniques in communication complexity
• A counterexample to the rank-coloring conjecture
• The Probabilistic Communication Complexity of Set Intersection
• A Bound for the Chromatic Number of a Graph
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• Rank and chromatic number of a graph
• The rank and size of graphs
• Modified ranks of tensors and the size of circuits

This page was built for publication: Matrix rank and communication complexity