Bounds for List-Decoding and List-Recovery of Random Linear Codes

DOI10.1109/TIT.2021.3127126MaRDI QIDQ5030334zbMATH OpenOpenAlexFDO

Authors Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters, Venkatesan Guruswami

Publication date 17 February 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.13247

zbMATH Keywords

boundslist size of random linear codeslist-decodinglist-recovery

Mathematics Subject Classification ID

Decoding (94B35) Other types of codes (94B60)

Abstract: 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 $Loinfty$, is known to be $1-h_q(p)$ for list-decoding, and $1-lo{g}_{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, $epsilon>0$ is the gap to capacity). (1) A random linear code of rate $1-lo{g}_q(ell)-epsilon$ requires list size $Lgeel{l}^{Omega(1/epsilon)}$ for list-recovery from input list size $ell$. This is surprisingly in contrast to completely random codes, where $L=O(ell/epsilon)$ suffices w.h.p. (2) A random linear code of rate $1-h_q(p)-epsilon$ requires list size $Lgelfloor{h}_q(p)/epsilon+0.99floor$ for list-decoding from error fraction $p$, when $epsilon$ is sufficiently small. (3) A random binary linear code of rate $1-h_2(p)-epsilon$ is list-decodable from average error fraction $p$ with list size with $Lleqlfloor{h}_2(p)/epsilonfloor+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.

Cited in

(8)

• On list decoding of certain \(\mathbb{F}_q\)-linear codes
• List Decoding of Biorthogonal Codes and the Hadamard Transform With Linear Complexity
• On List Recovery of High-Rate Tensor Codes
• scientific article; zbMATH DE number 7650135 (Why is no real title available?)
• Singleton-type bounds for list-decoding and list-recovery, and related results
• Point-polynomial incidences theorem with an application to Reed-Solomon codes
• Near-optimal list-recovery of linear code families
• List-recovery of random linear codes over small fields

This page was built for publication: Bounds for List-Decoding and List-Recovery of Random Linear Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5030334)