























In this work, we consider the list-decodability and list-recoverability of codes in the zero-rate regime. Briefly, a code $\mathcal{C} \subseteq [q]^n$ is $(p,\ell,L)$-list-recoverable if for all tuples of input lists $(Y_1,\dots,Y_n)$ with each $Y_i \subseteq [q]$ and $|Y_i|=\ell$ the number of codewords $c \in \mathcal{C}$ such that $c_i \notin Y_i$ for at most $pn$ choices of $i \in [n]$ is less than $L$; list-decoding is the special case of $\ell=1$. In recent work by Resch, Yuan and Zhang~(ICALP~2023) the zero-rate threshold for list-recovery was determined for all parameters: that is, the work explicitly computes $p_*:=p_*(q,\ell,L)$ with the property that for all $ε>0$ (a) there exist infinite families positive-rate $(p_*-ε,\ell,L)$-list-recoverable codes, and (b) any $(p_*+ε,\ell,L)$-list-recoverable code has rate $0$. In fact, in the latter case the code has constant size, independent on $n$. However, the constant size in their work is quite large in $1/ε$, at least $|\mathcal{C}|\geq (\frac{1}ε)^{O(q^L)}$. Our contribution in this work is to show that for all choices of $q,\ell$ and $L$ with $q \geq 3$, any $(p_*+ε,\ell,L)$-list-recoverable code must have size $O_{q,\ell,L}(1/ε)$, and furthermore this upper bound is complemented by a matching lower bound $Ω_{q,\ell,L}(1/ε)$. This greatly generalizes work by Alon, Bukh and Polyanskiy~(IEEE Trans.\ Inf.\ Theory~2018) which focused only on the case of binary alphabet (and thus necessarily only list-decoding). We remark that we can in fact recover the same result for $q=2$ and even $L$, as obtained by Alon, Bukh and Polyanskiy: we thus strictly generalize their work.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。