Simplified separation of information and communication
From MaRDI portal
Publication:4612484
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)
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)