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

In this work, we consider the list-decodability and list-recoverability of codes in the zero-rate regime. Briefly, a code C Ď rqsⁿ is (p, ℓ, L)-list-recoverable if for all tuples of input lists (Y₁, . . ., Y_n) with each Yi Ď rqs and |Yi| “ℓ, the number of codewords c P C such that ci R Yi for at most pn choices of i P rns 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 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| ě (¹_ε)^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 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. Our main technical contribution is to (a) properly define a linear programming relaxation of the list-recovery condition over large alphabets; and (b) to demonstrate that a certain function defined on a q-ary probability simplex is maximized by the uniform distribution. This represents the core challenge in generalizing to larger q (as a binary simplex can be naturally identified with a one-dimensional interval). We can subsequently re-utilize certain Schur convexity and convexity properties established for a related function by Resch, Yuan and Zhang along with ideas of Alon, Bukh and Polyanskiy.