Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR17-095 | 26th May 2017 17:49

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


Authors: Ran Gelles, Yael Tauman Kalai
Publication: 26th May 2017 20:33
Downloads: 102


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 $\Theta(\log n)$. This makes our lower bound for the cycle task tight.

ISSN 1433-8092 | Imprint