Constant-rate coding for multiparty interactive communication is impossible

Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

We study coding schemes for multiparty interactive communication over synchronous networks that suffer from stochastic noise, where each bit is independently flipped with probability e. We analyze the minimal overhead that must be added by the coding scheme in order to succeed in performing the computation despite the noise. Our main result is a lower bound on the communication of any noise-resilient protocol over a synchronous star network with n-parties (where all parties communicate in every round). Specifically, we show a task that can be solved by communicating T bits over the noise-free network, but for which any protocol with success probability of 1 - o(1) must communicate at least Ω(T log n/log log n) bits when the channels are noisy. By a 1 994 result of Rajagopalan and Schulman, the slowdown we prove is the highest one can obtain on any topology, up to a log log n factor. We complete our lower bound with a matching coding scheme that achieves the same overhead; thus, the capacity of (synchronous) star networks is Θ(log log n/log n). Our bounds prove that, despite several previous coding schemes with rate Ω(1) for certain topologies, no coding scheme with constant rate Ω(1) exists for arbitrary n-party noisy networks.

Original languageEnglish (US)
Title of host publicationSTOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
EditorsYishay Mansour, Daniel Wichs
PublisherAssociation for Computing Machinery
Pages999-1010
Number of pages12
ISBN (Electronic)9781450341325
DOIs
StatePublished - Jun 19 2016
Event48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 - Cambridge, United States
Duration: Jun 19 2016Jun 21 2016

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume19-21-June-2016
ISSN (Print)0737-8017

Other

Other48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016
CountryUnited States
CityCambridge
Period6/19/166/21/16

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Coding theory
  • Communication complexity
  • Interactive communication
  • Network topology
  • Rate
  • Stochastic noise

Fingerprint Dive into the research topics of 'Constant-rate coding for multiparty interactive communication is impossible'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., Efremenko, K., Gelles, R., & Haeupler, B. (2016). Constant-rate coding for multiparty interactive communication is impossible. In Y. Mansour, & D. Wichs (Eds.), STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (pp. 999-1010). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 19-21-June-2016). Association for Computing Machinery. https://doi.org/10.1145/2897518.2897563