Bridging the Capacity Gap Between Interactive and One-Way Communication
Bridging the Capacity Gap Between Interactive and One-Way Communication
复制标题
缩小交互式和单向通信之间的能力差距
DOI：
10.1137/1.9781611974782.138
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Velingker, Ameya
中科院分区：
文献类型：
--
作者：
Haeupler, Bernhard;Velingker, Ameya
我们研究了用于交互通信的编码方案的通信速率，该编码方案将任何两方交互协议转换为对噪声具有健壮性的协议。最近，Haeupler[11]证明，如果∊>；0部分的传输被恶意地或随机地破坏，则有可能获得通信速率。此外，Haeupler猜测，对于一般的输入协议，该速率是最优的。这与单向通信的经典设置不同，在经典设置中，纠错码可以达到1的最佳通信速率。在这项工作中，我们证明了对于非常自然的一类输入协议，在交互编码方案中也可以实现单向设置的二次较小的速率损失。我们引入了平均消息长度的概念，即在收到回复之前各方发送的平均比特数，作为衡量协议中交互程度的自然参数。此外，我们证明了具有平均消息长度ℓ=Ω(Poly(1/∊))的任何协议都可以被具有最优通信速率1-Θ(Η(∊)的协议模拟在错误分数为e的不经意的对抗信道上。此外，在附加的访问公共共享随机性的假设下，最优通信速率是无费率实现的，即通信速率自动适应于实际的差错率e而不必预先指定它。这表明，即使对于非常小的(e恒定的)平均消息长度，单向通信和交互通信之间的容量差距也可以被弥合，这很可能在许多应用中找到。
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 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 1In 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 ofaverage 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 — Θ(Η(∊)) over an oblivious adversarial channel with error fraction e. Furthermore, under the additional assumption of access to public shared randomness, the optimal communication rate is achievedratelessly, i.e., the communication rate adapts automatically to the actual error rate e 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 e) average message lengths, which are likely to be found in many applications.
登录
查看更多内容
针对对抗性噪声的快速交互式编码
DOI：
--
发表时间：
2014
期刊：
JACM
影响因子：
--
作者：
Zvika Brakerski;Y. Kalai;M. Naor
通讯作者：
M. Naor
针对对抗性噪声的高效交互式编码
DOI：
--
发表时间：
2012
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Zvika Brakerski;Y. Kalai
通讯作者：
Y. Kalai
交互式编码的最佳错误率 II：效率和列表解码
DOI：
--
发表时间：
2013
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
M. Ghaffari;Bernhard Haeupler
通讯作者：
Bernhard Haeupler
DOI：
--
发表时间：
1993
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
L. Schulman
通讯作者：
L. Schulman
交互式通信中针对最大错误的编码
影响因子：
2.5
作者：
M. Braverman;Anup Rao
通讯作者：
Anup Rao