ECCC-Report TR16-090https://eccc.weizmann.ac.il/report/2016/090Comments and Revisions published for TR16-090en-usFri, 03 Jun 2016 10:19:58 +0300
Paper TR16-090
| Bridging the Capacity Gap Between Interactive and One-Way Communication |
Bernhard Haeupler,
Ameya Velingker
https://eccc.weizmann.ac.il/report/2016/090We 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.Fri, 03 Jun 2016 10:19:58 +0300https://eccc.weizmann.ac.il/report/2016/090