Exponential separation of communication and external information

DOI10.1145/2897518.2897535MaRDI QIDQ5361895zbMATH OpenOpenAlexFDO

Authors Anat Ganor, Gillat Kol, 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

communication complexitycommunication compressioninformation complexity

Mathematics Subject Classification ID

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

Recommendations

• Exponential separation of communication and external information
• Exponential separation of information and communication for Boolean functions
• Exponential Separation of Information and Communication for Boolean Functions
• On information complexity in the broadcast model
• Simplified separation of information and communication

Cited in

(14)

• Information complexity and applications.
• The direct sum of universal relations
• Prediction from partial information and hindsight, with application to circuit lower bounds
• Relative discrepancy does not separate information and communication complexity
• Interactive Information Complexity
• Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
• Interactive information complexity
• Simplified separation of information and communication
• Compressing interactive communication under product distributions
• A candidate for a strong separation of information and communication
• Exponential separation of communication and external information
• Optimal separation and strong direct sum for randomized query complexity
• Query-to-communication lifting using low-discrepancy gadgets
• Exponential separation of information and communication for Boolean functions

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

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