Constant-rate coding for multiparty interactive communication is impossible

Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

Research output: Contribution to journalArticlepeer-review

9 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 ϵ. We analyze the minimal overhead that must be added by the coding scheme 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 nlog log n) bits when the channels are noisy. By a 1994 result of Rajagopalan and Schulman, the slowdown we prove is the highest one can obtain on any topology, up to a log logn 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 logn/ logn). 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)
Article numbera4
JournalJournal of the ACM
Volume65
Issue number1
DOIs
StatePublished - Dec 2017

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Coding theory
  • Communication complexity
  • Lower bounds
  • Multiparty interactive communication
  • Random noise
  • Star network

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

Cite this