Compressing Interactive Communication Under Product Distributions

DOI10.1137/16M109380XzbMath1391.68033OpenAlexW2795443780MaRDI QIDQ4637503

Alexander A. Sherstov

Publication date: 24 April 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/16m109380x

zbMATH Keywords

information theoryinformation complexitycommunication complexityinteractive compressionproduct distributionsprotocol compression

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Related Items

The communication complexity of functions with large outputs, The work of Mark Braverman, Unnamed Item, Exponential Separation of Communication and External Information

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• Towards a reverse Newman's theorem in interactive information complexity
• A discrepancy lower bound for information complexity
• An information statistics approach to data stream and communication complexity
• Probabilistic methods for algorithmic discrete mathematics
• How to Compress Interactive Communication
• Information Equals Amortized Communication
• Interactive Information Complexity
• The Communication Complexity of Correlation
• Internal Compression of Protocols to Entropy
• Exponential separation of communication and external information
• Interactive compression for product distributions
• Elements of Information Theory