Linear algebraic methods in communication complexity
From MaRDI portal
Publication:417541
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
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)
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
