Constant-rate coding for multiparty interactive communication is impossible

DOI10.1145/2897518.2897563MaRDI QIDQ5361897zbMATH OpenOpenAlexFDO

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

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

coding theorycommunication complexityinteractive communicationnetwork topologyratestochastic noise

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Network protocols (68M12) 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

• Constant-Rate Coding for Multiparty Interactive Communication Is Impossible
• scientific article; zbMATH DE number 6866311
• Reliable communication over highly connected noisy networks
• Reliable communication over highly connected noisy networks
• Interactive coding for multiparty protocols

Cited in

(10)

• Reliable communication over highly connected noisy networks
• Interactive non-malleable codes
• Constant-Rate Coding for Multiparty Interactive Communication Is Impossible
• scientific article; zbMATH DE number 6866311 (Why is no real title available?)
• Capacity of interactive communication over erasure channels and channels with feedback
• Making Asynchronous Distributed Computations Robust to Channel Noise
• Reliable communication over highly connected noisy networks
• Information dissemination via broadcasts in the presence of adversarial noise
• Computation over the noisy broadcast channel with malicious parties
• Noisy (binary) searching: simple, fast and correct

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 Q5361897)