Simplified separation of information and communication

DOI10.4086/TOC.2018.V014A020MaRDI QIDQ4612484zbMATH OpenOpenAlexFDO

Authors

Publication date 31 January 2019

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2018.v014a020

zbMATH Keywords

communication complexityinformation complexityfooling distributionseparation of complexity measures

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Exponential separation of information and communication for Boolean functions
• Exponential Separation of Information and Communication for Boolean Functions
• Relative discrepancy does not separate information and communication complexity
• Relative discrepancy does not separate information and communication complexity
• Exponential separation of communication and external information

Cites work

• A Mathematical Theory of Communication
• An information statistics approach to data stream and communication complexity
• Communication Complexity
• Compressing interactive communication under product distributions
• Computing with Noisy Information
• Exponential separation of communication and external information
• Exponential separation of information and communication for Boolean functions
• How to compress asymmetric communication
• How to compress interactive communication
• Information Equals Amortized Communication
• Interactive Information Complexity
• Interactive compression for product distributions
• Lower bounds on information complexity via zero-communication protocols and applications
• On the distributional complexity of disjointness
• Public vs private coin in bounded-round information
• Relative discrepancy does not separate information and communication complexity
• Some intersection theorems for ordered sets and graphs
• The Communication Complexity of Correlation
• The Probabilistic Communication Complexity of Set Intersection
• The communication complexity of addition

Cited in

(5)

• The communication complexity of functions with large outputs
• On the Communication Complexity of Key-Agreement Protocols.
• Exponential separation of communication and external information
• The work of Mark Braverman
• Exponential separation of communication and external information

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

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