论文标题
列表编码和列表重新发现的范围随机线性代码
Bounds for list-decoding and list-recovery of random linear codes
论文作者
论文摘要
如果对于家庭中的每个代码，则可以从错误分数$ p $列表中列表的校正代码列表来定位。据说如果输入列表尺寸$ \ ell $可以恢复列表，如果每个足够大的代码字（大小$ l $）或更多的代码字子集，则有一个坐标，代码字需要超过$ \ ell $值。在任何一种情况下，参数$ l $均为“清单大小”。容量，即这些概念的最大速率，即列表尺寸$ l \ to \ infty $，已知为$ 1-H_Q（P）$用于列表编码，而$ 1- \ log_q \ ell $ for List-Recovery，其中$ Q $是代码家族的字母尺寸。 在这项工作中，我们研究列表编码和列表重新发现的随机线性代码的列表大小，作为速率接近能力。我们显示了以下索赔在代码的选择上具有很高的可能性（下面，$ε> 0 $是容量的差距）。 （1）速率的随机线性代码$ 1- \ log_q（\ ell）-ε$要求列表大小$ l \ ge \ ell^{ω（1/ε）} $用于从输入列表size size $ \ ell $的列表重新发现。这与完全随机的代码相反，其中$ l = o（\ ell/ε）$ Suffices W.H.P. （2）速率的随机线性代码$ 1 -H_Q（p）-ε$需要列表尺寸$ l \ ge \ ge \ lfloor H_Q（p）/ε+0.99\ rfloor $，用于从错误分数$ p $中列表编码，当$ p $时，$ε$很小。 （3）随机二进制线性速率$ 1 -H_2（p）-ε$可从平均错误分数$ p $列表列表，列表大小，$ l \ leq \ lfloor H_2（p）/ε\ rfloor + 2 $。 第二和第三结果将二进制随机线性代码的列表大小固定在一起，用于列表编码和平均-radius列表编码为三个可能的值。
A family of error-correcting codes is list-decodable from error fraction $p$ if, for every code in the family, the number of codewords in any Hamming ball of fractional radius $p$ is less than some integer $L$ that is independent of the code length. It is said to be list-recoverable for input list size $\ell$ if for every sufficiently large subset of codewords (of size $L$ or more), there is a coordinate where the codewords take more than $\ell$ values. The parameter $L$ is said to be the "list size" in either case. The capacity, i.e., the largest possible rate for these notions as the list size $L \to \infty$, is known to be $1-h_q(p)$ for list-decoding, and $1-\log_q \ell$ for list-recovery, where $q$ is the alphabet size of the code family. In this work, we study the list size of random linear codes for both list-decoding and list-recovery as the rate approaches capacity. We show the following claims hold with high probability over the choice of the code (below, $ε> 0$ is the gap to capacity). (1) A random linear code of rate $1 - \log_q(\ell) - ε$ requires list size $L \ge \ell^{Ω(1/ε)}$ for list-recovery from input list size $\ell$. This is surprisingly in contrast to completely random codes, where $L = O(\ell/ε)$ suffices w.h.p. (2) A random linear code of rate $1 - h_q(p) - ε$ requires list size $L \ge \lfloor h_q(p)/ε+0.99 \rfloor$ for list-decoding from error fraction $p$, when $ε$ is sufficiently small. (3) A random binary linear code of rate $1 - h_2(p) - ε$ is list-decodable from average error fraction $p$ with list size with $L \leq \lfloor h_2(p)/ε\rfloor + 2$. The second and third results together precisely pin down the list sizes for binary random linear codes for both list-decoding and average-radius list-decoding to three possible values.
