2026-07-20T05:47:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18151 2024-03-06T11:01:09Z ddc:004 open_access

Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery Resch, Nicolas Yuan, Chen Zhang, Yihan Coding theory List-decoding List-recovery Zero-rate thresholds In this work we consider the list-decodability and list-recoverability of arbitrary q-ary codes, for all integer values of q ≥ 2. A code is called (p,L)_q-list-decodable if every radius pn Hamming ball contains less than L codewords; (p,𝓁,L)_q-list-recoverability is a generalization where we place radius pn Hamming balls on every point of a combinatorial rectangle with side length 𝓁 and again stipulate that there be less than L codewords. Our main contribution is to precisely calculate the maximum value of p for which there exist infinite families of positive rate (p,𝓁,L)_q-list-recoverable codes, the quantity we call the zero-rate threshold. Denoting this value by p_*, we in fact show that codes correcting a p_*+ε fraction of errors must have size O_ε(1), i.e., independent of n. Such a result is typically referred to as a "Plotkin bound." To complement this, a standard random code with expurgation construction shows that there exist positive rate codes correcting a p_*-ε fraction of errors. We also follow a classical proof template (typically attributed to Elias and Bassalygo) to derive from the zero-rate threshold other tradeoffs between rate and decoding radius for list-decoding and list-recovery. Technically, proving the Plotkin bound boils down to demonstrating the Schur convexity of a certain function defined on the q-simplex as well as the convexity of a univariate function derived from it. We remark that an earlier argument claimed similar results for q-ary list-decoding; however, we point out that this earlier proof is flawed. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nicolas Resch and Chen Yuan and Yihan Zhang 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.99 urn:nbn:de:0030-drops-181518 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.99 eng https://creativecommons.org/licenses/by/4.0/legalcode