Exponential separation of communication and external information
From MaRDI portal
Publication:5361895
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
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
