2023/09/04 by Resch, Nicolas, Yuan, Chen, Zhang, Yihan
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2309.01800
In this work, we consider the list-decodability and list-recoverability of codes in the zero-rate regime. Briefly, a code C ⊆ [q]n is (p,ℓ,L)-list-recoverable if for all tuples of input lists (Y1,…,Yn) with each Yi ⊆ [q] and |Yi|=ℓ the number of codewords c ∈ C such that ci ∉ Yi for at most pn choices of i ∈ [n] is less than L; list-decoding is the special case of ℓ=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,ℓ,L) with the property that for all ε>0 (a) there exist infinite families positive-rate (p_*-ε,ℓ,L)-list-recoverable codes, and (b) any (p_*+ε,ℓ,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 |C|≥ (\frac1ε)O(qL). Our contribution in this work is to show that for all choices of q,ℓ and L with q ≥ 3, any (p_*+ε,ℓ,L)-list-recoverable code must have size Oq,ℓ,L(1/ε), and furthermore this upper bound is complemented by a matching lower bound Ωq,ℓ,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.