conference paper published yes Nicolas Resch author Chen Yuan author Yihan Zhang author 2ce5da42-b2ea-11eb-bba5-9f264e9d002c0000-0002-6465-6258 MaMo department ICALP: Automata, Languages and Programming 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. https://research-explorer.ista.ac.at/download/14083/14091/2023_LIPIcsICALP_Resch.pdf application/pdfno Schloss Dagstuhl - Leibniz-Zentrum für Informatik2023Paderborn, Germany eng 1868-8969 9783959772785 2210.0775410.4230/LIPIcs.ICALP.2023.99 261 https://research-explorer.ista.ac.at/record/17330 N. Resch, C. Yuan, and Y. Zhang, “Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery,” in <i>50th International Colloquium on Automata, Languages, and Programming</i>, Paderborn, Germany, 2023, vol. 261. N. Resch, C. Yuan, Y. Zhang, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. Resch, Nicolas, et al. “Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery.” <i>50th International Colloquium on Automata, Languages, and Programming</i>, vol. 261, 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.99">10.4230/LIPIcs.ICALP.2023.99</a>. Resch N, Yuan C, Zhang Y. 2023. Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery. 50th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261, 99. Resch, N., Yuan, C., &#38; Zhang, Y. (2023). Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery. In <i>50th International Colloquium on Automata, Languages, and Programming</i> (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.99">https://doi.org/10.4230/LIPIcs.ICALP.2023.99</a> Resch, Nicolas, Chen Yuan, and Yihan Zhang. “Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery.” In <i>50th International Colloquium on Automata, Languages, and Programming</i>, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.99">https://doi.org/10.4230/LIPIcs.ICALP.2023.99</a>. Resch N, Yuan C, Zhang Y. Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery. In: <i>50th International Colloquium on Automata, Languages, and Programming</i>. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.99">10.4230/LIPIcs.ICALP.2023.99</a> 140832023-08-20T22:01:13Z2025-09-08T08:31:53Z