论文标题
代码合奏的阈值速率：线性最好
Threshold Rates of Codes Ensembles: Linear is Best
论文作者
论文摘要
在这项工作中，我们证明了有关随机线性代码的组合特性的新结果。 首先，我们证明了在$ \ MATHBB F_Q $ $ $ \ VAREPSILON $ -CLOSE上列出的列表大小的下限列表大小所需的列表大小，以便能够使用误差半径$ρ$和size $ \ ell $的输入列表。我们表明，列表大小的$ L $必须至少为$ \ frac {\ log_q \ binom {q} {\ ell} -r} -r} {\ varepsilon} $，其中$ r $是随机线性代码的速率。作为比较，我们还将随机代码的列表大小固定为$ \ frac {\ log_q \ binom {q} {\ ell}}} {\ varepsilon} $。这留下了（我们考虑的可能性），即随机线性代码的性能要比列表重新恢复性的随机代码更好，这与擦除列表重新发现的情况相反（Guruswami等人，IEEE TIT 2021B）。 接下来，我们考虑使用恒定列表大小的列表编码。具体而言，我们获得了新的下限，以$ \ MATHBB f_2 $的随机线性代码的$ 3 $可解释性列表的速率获得新的下限；和$ 2 $ 2 $可解释性的随机线性代码超过$ \ mathbb f_q $（对于任何$ q $）。这扩展了Guruswami等人。 （IEEE TIT 2021A）仅研究了$ 2 $ 2 $ 2 $可解释性线性代码超过$ \ Mathbb f_2 $。此外，在这两种情况下，我们都可以证明该速率大于均匀随机代码的速率。
In this work, we prove new results concerning the combinatorial properties of random linear codes. Firstly, we prove a lower bound on the list-size required for random linear codes over $\mathbb F_q$ $\varepsilon$-close to capacity to list-recover with error radius $ρ$ and input lists of size $\ell$. We show that the list-size $L$ must be at least $\frac{\log_q\binom{q}{\ell}-R}{\varepsilon}$, where $R$ is the rate of the random linear code. As a comparison, we also pin down the list size of random codes which is $\frac{\log_q\binom{q}{\ell}}{\varepsilon}$. This leaves open the possibility (that we consider likely) that random linear codes perform better than random codes for list-recoverability, which is in contrast to a recent gap shown for the case of list-recovery from erasures (Guruswami et al., IEEE TIT 2021B). Next, we consider list-decoding with constant list-sizes. Specifically, we obtain new lower bounds on the rate required for list-of-$3$ decodability of random linear codes over $\mathbb F_2$; and list-of-$2$ decodability of random linear codes over $\mathbb F_q$ (for any $q$). This expands upon Guruswami et al. (IEEE TIT 2021A) which only studied list-of-$2$ decodability of random linear codes over $\mathbb F_2$. Further, in both cases we are able to show that the rate is larger than that which is possible for uniformly random codes.
