Simplified separation of information and communication

DOI10.4086/TOC.2018.V014A020zbMATH Open1412.68060OpenAlexW2405665546MaRDI QIDQ4612484FDOQ4612484

Authors:

Publication date: 31 January 2019

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

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

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

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)

Cites Work

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

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)