The Communication Complexity of Correlation

DOI10.1109/TIT.2009.2034824zbMath1366.94020OpenAlexW1589803317MaRDI QIDQ4976061

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

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

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

Related Items

Communication with contextual uncertainty ⋮ Relative Discrepancy Does not Separate Information and Communication Complexity ⋮ Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications ⋮ Interactive Information Complexity ⋮ Interactive Information Complexity ⋮ Direct sum fails for zero-error average communication ⋮ Certifying equality with limited interaction ⋮ A discrepancy lower bound for information complexity ⋮ On rejection sampling in Lyubashevsky's signature scheme ⋮ Deterministic compression with uncertain priors ⋮ Compressing Interactive Communication Under Product Distributions ⋮ Communication complexity and the reality of the wave function ⋮ Multipartite quantum correlation and communication complexities ⋮ Simulation theorems via pseudo-random properties ⋮ Unnamed Item ⋮ Lifting Theorems for Equality ⋮ New bounds on classical and quantum one-way communication complexity ⋮ Unnamed Item ⋮ Information-based measure of nonlocality ⋮ Common Information, Noise Stability, and Their Extensions