Bounds for List-Decoding and List-Recovery of Random Linear Codes
Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary K. Wootters · IEEE Transactions on Information Theory · 2021
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$. It is said to be list-recoverable for input list size$\ell $if for every sufficiently large subset of at least$L$codewords, there is a coordinate where the codewords take more than$\ell $values. In this work, we study the list size ofrandom linear codesfor 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$q$is the alphabet size, and$ \varepsilon > 0$is the gap to capacity). (1) A random linear code of rate$1 - \log _{q}(\ell) - \varepsilon $requires list size$L \ge \ell ^{\Omega (1/ \varepsilon)}$for list-recovery from input list size$\ell $. (2) A random linear code of rate$1 - h_{q}(p) - \varepsilon $requires list size$L \ge \left \lfloor{ {h_{q}(p)/ \varepsilon +0.99}}\right \rfloor $for list-decoding from error fraction$p$. (3) A randombinarylinear code of rate$1 - h_{2}(p) - \varepsilon $is list-decodable fromaverageerror fraction$p$with list size with$L \leq \left \lfloor{ {h_{2}(p)/ \varepsilon }}\right \rfloor + 2$. Our lower bounds follow by exhibiting an explicit subset of codewords so that this subset—or some symbol-wise permutation of it—lies in a random linear code with high probability. Our upper bound follows by strengthening a result of (Li, Wootters, 2018).