Tight Bounds on List-Decodable and List-Recoverable Zero-Rate Codes

09/04/2023

∙

by   Nicolas Resch, et al.

∙

0

∙

share

In this work, we consider the list-decodability and list-recoverability of codes in the zero-rate regime. Briefly, a code 𝒞⊆ [q]^n is (p,ℓ,L)-list-recoverable if for all tuples of input lists (Y_1,…,Y_n) with each Y_i ⊆ [q] and |Y_i|=ℓ the number of codewords c ∈𝒞 such that c_i ∉ Y_i 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 |𝒞|≥ (1/ϵ)^O(q^L). 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 O_q,ℓ,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.