How to compress interactive communication

DOI10.1145/1806689.1806701MaRDI QIDQ2875133zbMATH OpenOpenAlexFDO

Authors Boaz Barak, Mark Braverman, Xi Chen, Anup Rao

Publication date 13 August 2014

Published in Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1806689.1806701

zbMATH Keywords

communication complexitycompressiondirect suminformation theory

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• How to compress interactive communication
• Interactive compression for product distributions
• Compressing interactive communication under product distributions
• Interactive compression to external information
• scientific article; zbMATH DE number 2038719

Cited in

(40)

• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
• Compressing communication in distributed protocols
• The choice and agreement problems of a random function
• The direct sum of universal relations
• Information-theoretic approximations of the nonnegative rank
• Lower bounds for number-in-hand multiparty communication complexity, made easy
• New strong direct product results in communication complexity
• Information complexity density and simulation of protocols
• Geometric stability via information theory
• How to compress interactive communication
• An interactive information odometer and applications
• The hardness of being private
• Towards a reverse Newman's theorem in interactive information complexity
• Relative discrepancy does not separate information and communication complexity
• Interactive Information Complexity
• Choosing, agreeing, and eliminating in communication complexity
• Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
• How to compress asymmetric communication
• Compressing interactive communication under product distributions
• Amortized Communication Complexity
• A candidate for a strong separation of information and communication
• Tight bounds for single-pass streaming complexity of the set cover problem
• Information lower bounds via self-reducibility
• scientific article; zbMATH DE number 7559107 (Why is no real title available?)
• Query-to-communication lifting for BPP using inner product
• Lower bounds for external memory integer sorting via network coding
• Interactive compression to external information
• Direct product via round-preserving compression
• Lower bounds for number-in-hand multiparty communication complexity, made easy
• Query-to-communication lifting using low-discrepancy gadgets
• Two-party direct-sum questions through the lens of multiparty communication complexity
• Interactive compression for multi-party protocol
• Communication lower bounds of key-agreement protocols via density increment arguments
• A hierarchy of constant communication complexity
• A strong direct sum theorem for distributional query complexity
• Ning Cai's work on communication complexity
• Channel simulation: theory and applications to lossy compression and differential privacy
• A strong direct sum theorem for distributional query complexity
• Choosing, agreeing, and eliminating in communication complexity
• How to communicate efficiently

This page was built for publication: How to compress interactive communication

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