Exponential separation of communication and external information

DOI10.1145/2897518.2897535zbMath1377.68079OpenAlexW2411019220MaRDI QIDQ5361895

Gillat Kol, Anat Ganor, Ran Raz

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2897518.2897535

zbMATH Keywords

information complexitycommunication complexitycommunication compression

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Related Items (13)

Relative Discrepancy Does not Separate Information and Communication Complexity ⋮ Interactive Information Complexity ⋮ Interactive Information Complexity ⋮ Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness ⋮ Unnamed Item ⋮ Information complexity and applications. ⋮ Compressing Interactive Communication Under Product Distributions ⋮ The direct sum of universal relations ⋮ Unnamed Item ⋮ Prediction from partial information and hindsight, with application to circuit lower bounds ⋮ Unnamed Item ⋮ Exponential Separation of Communication and External Information ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets

This page was built for publication: Exponential separation of communication and external information