Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-090 | 27th May 2016 21:17

Bridging the Capacity Gap Between Interactive and One-Way Communication

RSS-Feed




TR16-090
Authors: Bernhard Haeupler, Ameya Velingker
Publication: 3rd June 2016 10:19
Downloads: 1128
Keywords: 


Abstract:

We study the communication rate of coding schemes for interactive communication that transform any two-party interactive protocol into a protocol that is robust to noise.

Recently, Haeupler (FOCS '14) showed that if an \epsilon > 0 fraction of transmissions are corrupted, adversarially or randomly, then it is possible to achieve a communication rate of 1 - \widetilde{O}(\sqrt{\epsilon}). Furthermore, Haeupler conjectured that this rate is optimal for general input protocols. This stands in contrast to the classical setting of one-way communication in which error-correcting codes are known to achieve an optimal communication rate of 1 - \Theta(H(\epsilon)) = 1 - \widetilde{\Theta}(\epsilon).

In this work, we show that the quadratically smaller rate loss of the one-way setting can also be achieved in interactive coding schemes for a very natural class of input protocols. We introduce the notion of average message length, or the average number of bits a party sends before receiving a reply, as a natural parameter for measuring the level of interactivity in a protocol. Moreover, we show that any protocol with average message length \ell = \Omega(\mathrm{poly}(1/\epsilon)) can be simulated by a protocol with optimal communication rate 1 - \Theta(H(\epsilon)) over an oblivious adversarial channel with error fraction \epsilon. Furthermore, under the additional assumption of access to public shared randomness, the optimal communication rate is achieved ratelessly, i.e., the communication rate adapts automatically to the actual error rate \epsilon without having to specify it in advance.

This shows that the capacity gap between one-way and interactive communication can be bridged even for very small (constant in \epsilon) average message lengths, which are likely to be found in many applications.



ISSN 1433-8092 | Imprint