Compressing interactive communication under product distributions

DOI10.1137/16M109380XzbMATH Open1391.68033OpenAlexW2795443780WikidataQ130012019 ScholiaQ130012019MaRDI QIDQ4637503FDOQ4637503

Authors: 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

Recommendations

• Interactive compression for product distributions
• How to compress interactive communication
• Interactive compression for multi-party protocol
• How to compress interactive communication
• Interactive compression to external information

zbMATH Keywords

information theorycommunication complexityinformation 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)

Cites Work

• Elements of Information Theory
• A Mathematical Theory of Communication
• Probabilistic methods for algorithmic discrete mathematics
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• An information statistics approach to data stream and communication complexity
• How to compress interactive communication
• Information Equals Amortized Communication
• Parallel repetition: simplification and the no-signaling case
• Towards a reverse Newman's theorem in interactive information complexity
• Interactive Information Complexity
• Title not available (Why is that?)
• The Communication Complexity of Correlation
• Internal Compression of Protocols to Entropy
• Exponential separation of communication and external information
• Interactive compression for product distributions
• How to compress asymmetric communication

Cited In (10)

• The communication complexity of functions with large outputs
• How to compress interactive communication
• How to compress interactive communication
• Interactive compression to external information
• Exponential separation of communication and external information
• Simplified separation of information and communication
• The work of Mark Braverman
• A candidate for a strong separation of information and communication
• Interactive compression for product distributions
• Interactive compression for multi-party protocol

This page was built for publication: Compressing interactive communication under product distributions

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