The Communication Complexity of Correlation

DOI10.1109/TIT.2009.2034824MaRDI QIDQ4976061zbMATH OpenOpenAlexFDO

Authors Prahladh Harsha, Rahul Jain, David Allen McAllester, Jaikumar Radhakrishnan

Publication date 27 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/tit.2009.2034824

Mathematics Subject Classification ID

Network protocols (68M12) Analysis of algorithms and problem complexity (68Q25) Communication theory (94A05) Measures of information, entropy (94A17)

Cited in

(24)

• New bounds on classical and quantum one-way communication complexity
• The corruption bound, log-rank, and communication complexity
• Multipartite quantum correlation and communication complexities
• Simulation theorems via pseudo-random properties
• Direct sum fails for zero-error average communication
• Certifying equality with limited interaction
• Relative discrepancy does not separate information and communication complexity
• Lower bounds on information complexity via zero-communication protocols and applications
• Interactive Information Complexity
• Trading information complexity for error
• Interactive information complexity
• Simplified separation of information and communication
• Compressing interactive communication under product distributions
• Lifting Theorems for Equality
• Communication complexity and the reality of the wave function
• Correlation in Hard Distributions in Communication Complexity
• Information-based measure of nonlocality
• Common Information, Noise Stability, and Their Extensions
• Deterministic compression with uncertain priors
• On rejection sampling in Lyubashevsky's signature scheme
• A direct product theorem for quantum communication complexity with applications to device-independent cryptography
• Ning Cai's work on communication complexity
• Channel simulation: theory and applications to lossy compression and differential privacy
• Quantum broadcast channel simulation via multipartite convex splitting

This page was built for publication: The Communication Complexity of Correlation

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