The Communication Complexity of Non-signaling Distributions

DOI10.1007/978-3-642-03816-7_24zbMath1250.68107arXiv0804.4859OpenAlexW1914859158MaRDI QIDQ3182931

Sophie Laplante, Julien Degorre, Jérémie Roland, M. A. Kaplan

Publication date: 16 October 2009

Published in: Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0804.4859

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (8)

Unbounded Bell violations for quantum genuine multipartite non-locality ⋮ Unbounded violations of bipartite Bell inequalities via operator space theory ⋮ Categorical Probabilistic Theories ⋮ Bell's nonlocality in a general nonsignaling case: Quantitatively and conceptually ⋮ Optimal non-signalling violations via tensor norms ⋮ The Hilbertian tensor norm and entangled two-prover games ⋮ Large violation of Bell inequalities with low entanglement ⋮ On the existence of a local quasi hidden variable (LqHV) model for each N-qudit state and the maximal quantum violation of Bell inequalities

Cites Work

• Complexity measures of sign matrices
• Towards quantifying non-local information transfer: finite-bit non-locality
• Tensor products and probability weights
• Tensor products in generalized measure theory
• Bell Inequalities with Auxiliary Communication
• On the power of quantum fingerprinting
• Simulating Quantum Correlations with Finite Communication
• Tensor Norms and the Classical Communication Complexity of Nonlocal Quantum Measurement
• Communication Complexity
• Approximating the Cut-Norm via Grothendieck's Inequality
• Lower bounds in communication complexity based on factorization norms

This page was built for publication: The Communication Complexity of Non-signaling Distributions