论文标题
列表可调节性，半径较大，用于芦苇 - 固体代码
List-decodability with large radius for Reed-Solomon codes
论文作者
论文摘要
芦苇 - 固体代码的列表可调节性引起了很多关注，但是参数之间最有可能的依赖性仍然没有得到充分理解。在这项工作中，我们专注于列表编码半径为$ r = 1- \ varepsilon $ for $ \ varepsilon $趋于零的情况。我们的主要结果指出，存在带有$ $ω（\ varepsilon）$的芦苇 - 固体代码，该代码为$（1- \ varepsilon，o（1/\ varepsilon））$ - 列表可解码，这意味着任何Radius $ 1- \ varepsilon $都包含的任何hamming Ball concips in Docsilos $ o（1/\ varepsilon $ o（1/\ vareps）。对于列表大小的任何代码小于块长度中的指数的代码，速率和列表编码半径之间的这种权衡是最有可能的。 通过实现速率和列表划分半径之间的权衡，我们改善了郭，李，汉古安，塔莫和wootters的最新结果，并解决了他们的工作的主要激励问题。此外，尽管它们的结果要求在块长度上呈指数级的字段，但我们只需要字段大小在多项式上很大（实际上，几乎是线性的就足够了）。我们从更一般的定理中推断出我们的主要结果，在该定理中，我们证明了任何给定代码的随机标点的良好列表可解码性属性，距离很大。
List-decodability of Reed-Solomon codes has received a lot of attention, but the best-possible dependence between the parameters is still not well-understood. In this work, we focus on the case where the list-decoding radius is of the form $r=1-\varepsilon$ for $\varepsilon$ tending to zero. Our main result states that there exist Reed-Solomon codes with rate $Ω(\varepsilon)$ which are $(1-\varepsilon, O(1/\varepsilon))$-list-decodable, meaning that any Hamming ball of radius $1-\varepsilon$ contains at most $O(1/\varepsilon)$ codewords. This trade-off between rate and list-decoding radius is best-possible for any code with list size less than exponential in the block length. By achieving this trade-off between rate and list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and Wootters, and resolve the main motivating question of their work. Moreover, while their result requires the field to be exponentially large in the block length, we only need the field size to be polynomially large (and in fact, almost-linear suffices). We deduce our main result from a more general theorem, in which we prove good list-decodability properties of random puncturings of any given code with very large distance.
