Algebraic techniques in communication complexity

DOI10.1016/0020-0190(95)00158-9MaRDI QIDQ1350289zbMATH OpenOpenAlexFDO

Authors Bruno Codenotti, Giovanni Manzini, Luciano Margara

Publication date 27 February 1997

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(95)00158-9

zbMATH Keywords

Communication complexityComputational complexityGapRank of a matrix

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Linear algebraic methods in communication complexity
• Complexity Lower Bounds using Linear Algebra
• On rank vs. communication complexity
• On the ``log rank-conjecture in communication complexity

Cites work

• A combinatorial approach to complexity
• Communication in bounded depth circuits
• Maximum Rank of Powers of a Matrix of a Given Pattern
• Modified ranks of tensors and the size of circuits
• On rank vs. communication complexity
• On the ``log rank-conjecture in communication complexity

Cited in

(6)

• Communication complexity and combinatorial lattice theory
• Matrix rank and communication complexity
• Complexity Lower Bounds using Linear Algebra
• Linear algebraic methods in communication complexity
• scientific article; zbMATH DE number 1223708 (Why is no real title available?)
• scientific article; zbMATH DE number 6308216 (Why is no real title available?)

This page was built for publication: Algebraic techniques in communication complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1350289)