Exponential Separation of Communication and External Information
From MaRDI portal
Publication:4997310
DOI10.1137/16M1096293zbMath1464.68101OpenAlexW2982055366WikidataQ115525627 ScholiaQ115525627MaRDI QIDQ4997310
Gillat Kol, Anat Ganor, Ran Raz
Publication date: 29 June 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/16m1096293
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Communication complexity, information complexity (68Q11)
Related Items (3)
The communication complexity of functions with large outputs ⋮ The work of Mark Braverman ⋮ Communication and information complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A discrepancy lower bound for information complexity
- The communication complexity of addition
- 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 in Communication Complexity
- Relative Discrepancy Does not Separate Information and Communication Complexity
- Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
- Interactive Information Complexity
- The Probabilistic Communication Complexity of Set Intersection
- Compressing Interactive Communication Under Product Distributions
- Communication Complexity
- Interactive compression to external information
- Internal Compression of Protocols to Entropy
- Exponential separation of communication and external information
- Interactive compression for product distributions
- Exponential Separation of Information and Communication for Boolean Functions
This page was built for publication: Exponential Separation of Communication and External Information