Lower bounds in communication complexity based on factorization norms

DOI10.1145/1250790.1250892zbMath1232.68067OpenAlexW1982568420MaRDI QIDQ5900542

Adi Shraibman, Nathan Linial

Publication date: 5 January 2009

Published in: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1250790.1250892

zbMATH Keywords

lower boundsentanglementquantum communication complexityrandomized communication complexityfactorization norms

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Communication theory (94A05) Quantum information, communication, networks (quantum-theoretic aspects) (81P45)

Related Items (7)

Hellinger volume and number-on-the-forehead communication complexity ⋮ Approximate nonnegative rank is equivalent to the smooth rectangle bound ⋮ A generalized Grothendieck inequality and nonlocal correlations that require high entanglement ⋮ The Hilbertian tensor norm and entangled two-prover games ⋮ Unbounded-Error Classical and Quantum Communication Complexity ⋮ Grothendieck’s Theorem, past and present ⋮ On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity

This page was built for publication: Lower bounds in communication complexity based on factorization norms