License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2017.21
URN: urn:nbn:de:0030-drops-81523
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8152/
Go to the corresponding LIPIcs Volume Portal

Gelles, Ran ; T. Kalai, Yael

Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks

pdf-format:
LIPIcs-ITCS-2017-21.pdf (0.5 MB)

Abstract

Multiparty interactive coding allows a network of n parties to perform distributed computations when the communication channels suffer from noise. Previous results (Rajagopalan and Schulman, STOC’94) obtained a multiparty interactive coding protocol, resilient to random noise, with a blowup of O(log(\Delta + 1)) for networks whose topology has a maximal degree \Delta. Vitally, the communication model in their work forces all the parties to send one message at every round of the protocol, even if they have nothing to send.

We re-examine the question of multiparty interactive coding, lifting the requirement that forces all the parties to communicate at each and every round. We use the recently developed information-theoretic machinery of Braverman et al. (STOC ’16) to show that if the network’s topology is a cycle, then there is a specific “cycle task” for which any coding scheme has a communication blowup of \Omega(log n). This is quite surprising since the cycle has a maximal degree of \Delta = 2, implying a coding with a constant blowup when all parties are forced to speak at all rounds.

We complement our lower bound with a matching coding scheme for the "cycle task" that has a communication blowup of \Omega(log n). This makes our lower bound for the cycle task tight.

BibTeX - Entry

@InProceedings{gelles_et_al:LIPIcs:2017:8152,
  author =	{Ran Gelles and Yael T. Kalai},
  title =	{{Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Christos H. Papadimitriou},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8152},
  URN =		{urn:nbn:de:0030-drops-81523},
  doi =		{10.4230/LIPIcs.ITCS.2017.21},
  annote =	{Keywords: Interactive Communication, Coding, Stochastic Noise, Communication Complexity}
}

Keywords: Interactive Communication, Coding, Stochastic Noise, Communication Complexity
Collection: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Issue Date: 2017
Date of publication: 28.11.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI