Linear algebraic methods in communication complexity

DOI10.1016/J.LAA.2011.07.008MaRDI QIDQ417541zbMATHOpenAlexFDO

Authors L. Deaett, Venkatesh Srinivasan

Publication date 14 May 2012

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

Full work available at URL https://doi.org/10.1016/j.laa.2011.07.008

zbMATH Keywords

randomizationcommunication complexityminimum rankmatrix ranksign rank

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Basic linear algebra (15A99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Algebraic techniques in communication complexity
• Complexity Lower Bounds using Linear Algebra
• On rank vs. communication complexity
• Harmonic analysis, real approximation, and the communication complexity of Boolean functions
• Communication Complexity

Cites work

• scientific article; zbMATH DE number 3967876 (Why is no real title available?)
• scientific article; zbMATH DE number 3482343 (Why is no real title available?)
• scientific article; zbMATH DE number 1219592 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• A linear lower bound on the unbounded error probabilistic communication complexity.
• A note on minimum rank and maximum nullity of sign patterns
• Communication Complexity
• Communication complexity and combinatorial lattice theory
• Complexity Lower Bounds using Linear Algebra
• Computational Complexity
• Expressing combinatorial optimization problems by linear programs
• Lower bounds for predecessor searching in the cell probe model
• Matrix rank and communication complexity
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• On rank vs. communication complexity
• Probabilistic communication complexity
• Quick approximation to matrices and applications
• Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
• The Sign-Rank of AC$^0$
• The minimum rank of symmetric matrices described by a graph: a survey
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

Cited in

(10)

• scientific article; zbMATH DE number 1760022 (Why is no real title available?)
• On rank vs. communication complexity
• Orthogonal representations of Steiner triple system incidence graphs
• On Blocky Ranks Of Matrices
• Coordination and discoordination in linear algebra, linear information theory, and coded caching
• Complexity Lower Bounds using Linear Algebra
• scientific article; zbMATH DE number 1223708 (Why is no real title available?)
• Linear decomposition method in analyzing hidden information protocols on algebraic platforms
• Dimension-free bounds and structural results in communication complexity
• Linear space bootstrap communication schemes

This page was built for publication: Linear algebraic methods in communication complexity

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