Nexus Trimester - 2016 - Central Workshop

Collection Nexus Trimester - 2016 - Central Workshop

Organizer(s)
Date(s) 03/05/2024
00:00:00 / 00:00:00
8 20

Constant-rate coding for multiparty interactive communication is impossible

By Ran Gelles

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 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 star network with n-parties. Specifically, we show a task that can be solved by communicating Tn bits over the noise-free network, but for which any protocol with success probability of 1−o(1) must communicate at least Ω(Tn log n /log 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 log n factor. We complete our lower bound with a matching coding scheme that achieves the same overhead; thus, the capacity of 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.

Information about the video

  • Date of recording 02/03/2016
  • Date of publication 14/03/2016
  • Institution IHP
  • Format MP4

Domain(s)

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow




Register

  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
    community
  • Get notification updates
    for your favorite subjects
Give feedback