Constant-Rate Coding for Multiparty Interactive Communication Is Impossible

DOI10.1145/3050218zbMath1426.68016OpenAlexW2772918851MaRDI QIDQ3177892

Bernhard Haeupler, Mark Braverman, Klim Efremenko, Ran Gelles

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 boundscoding theorycommunication complexityrandom noisestar networkmultiparty interactive communication

Mathematics Subject Classification ID

Communication networks in operations research (90B18) 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Network protocols (68M12) Communication theory (94A05)

Related Items (5)

Distributed computations in fully-defective networks ⋮ Unnamed Item ⋮ The work of Mark Braverman ⋮ Making asynchronous distributed computations robust to noise ⋮ Noisy beeping networks

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