Constant-Rate Coding for Multiparty Interactive Communication Is Impossible

DOI10.1145/3050218MaRDI QIDQ3177892zbMATH OpenOpenAlexFDO

Authors Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

Publication date 2 August 2018

Published in Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsrandom noisecommunication complexitycoding theorystar networkmultiparty interactive communication

Mathematics Subject Classification ID

Communication theory (94A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Communication networks in operations research (90B18) Network protocols (68M12)

Recommendations

• Constant-rate coding for multiparty interactive communication is impossible
• scientific article; zbMATH DE number 6866311
• Constant-Rate Interactive Coding Is Impossible, Even in Constant-Degree Networks
• Towards optimal deterministic coding for interactive communication
• Worst Case Nonzero-Error Interactive Communication
• Toward coding for maximum errors in interactive communication
• Explicit Capacity Approaching Coding for Interactive Communication
• Efficient Multiparty Interactive Coding—Part II: Non-Oblivious Noise
• The Infinite-Message Limit of Two-Terminal Interactive Source Coding
• Interactive coding over the noisy broadcast channel

Cited in

(8)

• Noisy beeping networks
• Making asynchronous distributed computations robust to noise
• Reliable communication over highly connected noisy networks
• Reliable communication over highly connected noisy networks
• Algorithms for noisy broadcast with erasures
• The work of Mark Braverman
• scientific article; zbMATH DE number 6866311 (Why is no real title available?)
• Constant-rate coding for multiparty interactive communication is impossible

This page was built for publication: Constant-Rate Coding for Multiparty Interactive Communication Is Impossible

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