Lower bounds in communication complexity based on factorization norms

DOI10.1002/RSA.20232MaRDI QIDQ5902088zbMATH OpenOpenAlexFDO

Authors Nathan Linial, Adi Shraibman

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 spacescommunication complexityfactorization normslower bounds

Mathematics Subject Classification ID

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

Recommendations

• A Lower Bound on Entanglement-Assisted Quantum Communication Complexity
• Lower Bounds for Quantum Communication Complexity
• Kolmogorov Complexity and Combinatorial Methods in Communication Complexity
• Lower bounds on information complexity via zero-communication protocols and applications
• Communication Lower Bounds Via the Chromatic Number

Cites work

• Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states
• Complexity measures of sign matrices
• Fourier analysis for probabilistic communication complexity
• Harmonic analysis, real approximation, and the communication complexity of Boolean functions
• scientific article; zbMATH DE number 1263236 (Why is no real title available?)
• Learning complexity vs communication complexity
• On ``bent functions
• On quantum and probabilistic communication: Las Vegas and one-way protocols
• On rank vs. communication complexity
• Quantum communication complexity of symmetric predicates

Cited in

(26)

• Classical versus quantum communication in XOR games
• Upper bounds on communication in terms of approximate rank
• Grothendieck constant is norm of Strassen matrix multiplication tensor
• Kolmogorov width and approximate rank
• Dimension-free bounds and structural results in communication complexity
• The multiparty communication complexity of set disjointness
• Grothendieck-type inequalities in combinatorial optimization
• The Communication Complexity of Non-signaling Distributions
• Lower bounds on information complexity via zero-communication protocols and applications
• A strong direct product theorem for quantum query complexity
• scientific article; zbMATH DE number 4030953 (Why is no real title available?)
• On a theorem of Razborov
• Approximate Degree in Classical and Quantum Computing
• scientific article; zbMATH DE number 7559121 (Why is no real title available?)
• Sign rank vs discrepancy
• Kolmogorov complexity and combinatorial methods in communication complexity
• A Lower Bound on Entanglement-Assisted Quantum Communication Complexity
• Communication lower bounds using directional derivatives
• Around the log-rank conjecture
• Upper bounds on communication in terms of approximate rank
• Factorization norms and an inverse theorem for MaxCut
• Separation of the factorization norm and randomized communication complexity
• Communication complexity and discrepancy of halfplanes
• Large violation of Bell inequalities with low entanglement
• Positive semidefinite rank
• On convex complexity measures

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5902088)