Lower bounds in communication complexity based on factorization norms

DOI10.1002/rsa.20232zbMath1202.94012OpenAlexW4256261794MaRDI QIDQ5902088

Adi Shraibman, Nathan Linial

Publication date: 16 June 2009

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20232

zbMATH Keywords

Banach spaceslower boundscommunication complexityfactorization norms

Mathematics Subject Classification ID

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

Related Items (20)

Grothendieck-Type Inequalities in Combinatorial Optimization ⋮ Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications ⋮ Approximate Degree in Classical and Quantum Computing ⋮ The Communication Complexity of Non-signaling Distributions ⋮ Classical versus quantum communication in XOR games ⋮ A strong direct product theorem for quantum query complexity ⋮ Around the log-rank conjecture ⋮ Kolmogorov width and approximate rank ⋮ Dimension-free bounds and structural results in communication complexity ⋮ On a theorem of Razborov ⋮ On convex complexity measures ⋮ Kolmogorov complexity and combinatorial methods in communication complexity ⋮ Large violation of Bell inequalities with low entanglement ⋮ Unnamed Item ⋮ Positive semidefinite rank ⋮ The Multiparty Communication Complexity of Set Disjointness ⋮ Sign rank vs discrepancy ⋮ Communication Lower Bounds Using Directional Derivatives ⋮ Grothendieck constant is norm of Strassen matrix multiplication tensor ⋮ Upper bounds on communication in terms of approximate rank

Cites Work

• Unnamed Item
• Complexity measures of sign matrices
• On ``bent functions
• Harmonic analysis, real approximation, and the communication complexity of Boolean functions
• On rank vs. communication complexity
• Fourier analysis for probabilistic communication complexity
• On quantum and probabilistic communication
• Learning Complexity vs Communication Complexity
• Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states
• Quantum communication complexity of symmetric predicates

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