Constant-rate coding for multiparty interactive communication is impossible

DOI10.1145/2897518.2897563zbMath1373.68038OpenAlexW2419372578MaRDI QIDQ5361897

Klim Efremenko, Mark Braverman, Bernhard Haeupler, Ran Gelles

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 complexityratenetwork topologystochastic noiseinteractive communication

Mathematics Subject Classification ID

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

Related Items (5)

Interactive non-malleable codes ⋮ Making Asynchronous Distributed Computations Robust to Channel Noise ⋮ Reliable communication over highly connected noisy networks ⋮ Capacity of Interactive Communication over Erasure Channels and Channels with Feedback ⋮ Unnamed Item

This page was built for publication: Constant-rate coding for multiparty interactive communication is impossible