Constant-Rate Coding for Multiparty Interactive Communication Is Impossible

DOI10.1145/3050218zbMATH Open1426.68016OpenAlexW2772918851MaRDI QIDQ3177892FDOQ3177892

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

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

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)

Cited In (9)

• 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
• Title not available (Why is that?)
• Constant-rate coding for multiparty interactive communication is impossible
• Distributed computations in fully-defective networks

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)