Linear algebraic methods in communication complexity

DOI10.1016/j.laa.2011.07.008zbMath1278.68106OpenAlexW2000545126MaRDI QIDQ417541

Louis 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 complexitymatrix rankminimum ranksign rank

Mathematics Subject Classification ID

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

Related Items (1)

Orthogonal representations of Steiner triple system incidence graphs

Cites Work

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

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