Lower Bounds in Communication Complexity

DOI10.1561/0400000040zbMath1193.94002OpenAlexW4297970684MaRDI QIDQ3404184

Adi Shraibman, Troy Lee

Publication date: 8 February 2010

Published in: Foundations and Trends in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1561/0400000040

zbMATH Keywords

computational complexitylower boundsinformation theorycommunication complexity

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Research exposition (monographs, survey articles) pertaining to information and communication theory (94-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Information theory (general) (94A15) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (24)

Grothendieck-Type Inequalities in Combinatorial Optimization ⋮ Heuristics for exact nonnegative matrix factorization ⋮ Amplification of One-Way Information Complexity via Codes and Noise Sensitivity ⋮ Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications ⋮ Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank ⋮ Approximate Degree in Classical and Quantum Computing ⋮ Bounds on the number of 2-level polytopes, cones, and configurations ⋮ Around the log-rank conjecture ⋮ Unnamed Item ⋮ Approximate nonnegative rank is equivalent to the smooth rectangle bound ⋮ Unnamed Item ⋮ Dimension-free bounds and structural results in communication complexity ⋮ Information complexity and applications. ⋮ String Matching: Communication, Circuits, and Learning. ⋮ Tight Bounds on Communication Complexity of Symmetric XOR Functions in One-Way and SMP Models ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Counting the number of perfect matchings, and generalized decision trees ⋮ Lower bounds on nonnegative rank via nonnegative nuclear norms ⋮ Fooling Pairs in Randomized Communication Complexity ⋮ Exponential Separation of Communication and External Information ⋮ Quantum State Complexity of Formal Languages ⋮ A Lifting Theorem with Applications to Symmetric Functions ⋮ Upper bounds on communication in terms of approximate rank

This page was built for publication: Lower Bounds in Communication Complexity