Paper Info
Title
Bridging the Capacity Gap Between Interactive and One-Way Communication.
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 [11] showed that if an ϵ > 0 fraction of transmissions are corrupted, adversarially or randomly, then it is possible to achieve a communication rate of [EQUATION]. 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 − Θ (H(ϵ)) = 1 − O (ϵ). 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 ℓ = Ω(poly(1/ϵ)) can be simulated by a protocol with optimal communication rate 1 − Θ(H(ϵ)) over an oblivious adversarial channel with error fraction ϵ. 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 ϵ 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 ϵ) average message lengths, which are likely to be found in many applications.
Year
DOI
Venue
2016
10.1137/1.9781611974782.138
SODA
DocType
Citations 
PageRank 
Journal
4
0.55
References 
Authors
6
2
Name
Order
Citations
PageRank
Bernhard Haeupler162854.00
Ameya Velingker2354.95