Average-radius list-recoverability of random linear codes
Average-radius list-recoverability of random linear codes
复制标题
随机线性码的平均半径列表可恢复性
DOI：
10.1137/1.9781611975031.42
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Mary Wootters
中科院分区：
文献类型：
--
作者：
A. Rudra;Mary Wootters
我们分析了随机线性码的列表可解码性和相关概念。这在以前已经被广泛地研究过：有许多不同的参数体系和许多不同的变体。以前的作品使用了互补的论证风格——每个都在自己的参数体系中工作，而不是在其他体系中工作——而且在我们对随机线性代码的列表可解码性的理解上留下了一些空白。特别是，这些参数都不适用于列表恢复，这是列表解码的一种概括，在各种设置中都很有用。在这项工作中，我们提出了一种新的方法，它可以跨参数体系工作，并进一步推广到列表恢复。特别是，我们的参数为大字段上的列表解码和列表恢复提供了更好的结果；改进的（拟多项式）列表大小用于随机线性码的高速率列表恢复改进的列表解码算法结果；和最佳平均半径列表解码恒定大小的字母。
We analyze the list-decodability, and related notions, of random linear codes. This has been studied extensively before: there are many different parameter regimes and many different variants. Previous works have used complementary styles of arguments---which each work in their own parameter regimes but not in others---and moreover have left some gaps in our understanding of the list-decodability of random linear codes. In particular, none of these arguments work well for list-recovery, a generalization of list-decoding that has been useful in a variety of settings. In this work, we present a new approach, which works across parameter regimes and further generalizes to list-recovery. In particular, our argument provides better results for list-decoding and list-recovery over large fields; improved (quasipolynomial) list sizees for high-rate list-recovery of random linear codes; improved algorithmic results for list-decoding; and optimal average-radius list-decoding over constant-sized alphabets.