Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding
Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding
复制标题
交互式编码的最佳错误率 II：效率和列表解码
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Bernhard Haeupler
中科院分区：
文献类型：
--
作者：
M. Ghaffari;Bernhard Haeupler
我们在交互式通信中研究编码方案。 ，沟通复杂性n和计算复杂性。非适应性编码方案具有接近线性的计算复杂性，并耐受任何错误率Δ<; 1/4;在这些措施中，我们还为其他感兴趣的设置提供了结果，即耐受ρ<的第一个计算和沟通有效方案；和ρ <; 1/2允许这些解码。减少在各种设置中降低了独特的解码，以列出解码。
We study coding schemes for error correction in interactive communications. Such interactive coding schemes simulate any n-round interactive protocol using N rounds over an adversarial channel that corrupts up to ρN transmissions. Important performance measures for a coding scheme are its maximum tolerable error rate ρ, communication complexity N, and computational complexity. We give the first coding scheme for the standard setting which performs optimally in all three measures: Our randomized non-adaptive coding scheme has a near-linear computational complexity and tolerates any error rate δ <; 1/4 with a linear N = Θ(n) communication complexity. This improves over prior results [1]-[4] which each performed well in two of these measures. We also give results for other settings of interest, namely, the first computationally and communication efficient schemes that tolerate ρ <; 2/7 adaptively, ρ <; 1/3 if only one party is required to decode, and ρ <; 1/2 if list decoding is allowed. These are the optimal tolerable error rates for the respective settings. These coding schemes also have near linear computational and communication complexity. These results are obtained via two techniques: We give a general black-box reduction which reduces unique decoding, in various settings, to list decoding. We also show how to boost the computational and communication efficiency of any list decoder to become near linear1.