Linear algebraic methods in communication complexity
DOI10.1016/J.LAA.2011.07.008zbMATH Open1278.68106OpenAlexW2000545126MaRDI QIDQ417541FDOQ417541
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Basic linear algebra (15A99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Computational Complexity
- Expressing combinatorial optimization problems by linear programs
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
- Communication Complexity
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
- A linear lower bound on the unbounded error probabilistic communication complexity.
- The Sign-Rank of AC$^0$
- Complexity Lower Bounds using Linear Algebra
- Probabilistic communication complexity
- Quick approximation to matrices and applications
- The minimum rank of symmetric matrices described by a graph: a survey
- Title not available (Why is that?)
- Communication complexity and combinatorial lattice theory
- On rank vs. communication complexity
- Matrix rank and communication complexity
- Lower bounds for predecessor searching in the cell probe model
- A note on minimum rank and maximum nullity of sign patterns
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (10)
- Complexity Lower Bounds using Linear Algebra
- Dimension-free bounds and structural results in communication complexity
- Title not available (Why is that?)
- Coordination and discoordination in linear algebra, linear information theory, and coded caching
- On rank vs. communication complexity
- Linear space bootstrap communication schemes
- On Blocky Ranks Of Matrices
- Title not available (Why is that?)
- Orthogonal representations of Steiner triple system incidence graphs
- Linear decomposition method in analyzing hidden information protocols on algebraic platforms
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)
