---
OA_place: publisher
OA_type: gold
_id: '19281'
abstract:
- lang: eng
  text: "In this work, we consider the list-decodability and list-recoverability of
    codes in the zero-rate regime. Briefly, a code \U0001D49E ⊆ [q]ⁿ is (p,\U0001D4C1,L)-list-recoverable
    if for all tuples of input lists (Y₁,… ,Y_n) with each Y_i ⊆ [q] and |Y_i| = \U0001D4C1,
    the number of codewords c ∈ \U0001D49E 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 \U0001D4C1 = 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,\U0001D4C1,L) with the property that for all ε > 0 (a) there
    exist positive-rate (p_*-ε,\U0001D4C1,L)-list-recoverable codes, and (b) any (p_*+ε,\U0001D4C1,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
    |\U0001D49E| ≥ (1/(ε))^O(q^L).\r\nOur contribution in this work is to show that
    for all choices of q,\U0001D4C1 and L with q ≥ 3, any (p_*+ε,\U0001D4C1,L)-list-recoverable
    code must have size O_{q,\U0001D4C1,L}(1/ε), and furthermore this upper bound
    is complemented by a matching lower bound Ω_{q,\U0001D4C1,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.
    \r\nOur 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."
acknowledgement: "The research of C. Yuan was support in part by the National Key
  R&D Program of China\r\nunder Grant 2023YFE0123900 and Natural Science Foundation
  of Shanghai under the 2024 Shanghai Action Plan for Science, Technology and Innovation
  Grant 24BC3200700. The research of N. Resch is supported in part by an NWO (Dutch
  Research Council) grant with number C.2324.0590, and this work was done in part
  while he was visiting the Simons Institute for the Theory of Computing, supported
  by DOE grant #DE-SC0024124."
alternative_title:
- LIPIcs
article_number: '82'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Nicolas
  full_name: Resch, Nicolas
  last_name: Resch
- first_name: Chen
  full_name: Yuan, Chen
  last_name: Yuan
- first_name: Yihan
  full_name: Zhang, Yihan
  id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
  last_name: Zhang
  orcid: 0000-0002-6465-6258
citation:
  ama: 'Resch N, Yuan C, Zhang Y. Tight bounds on list-decodable and list-recoverable
    zero-rate codes. In: <i>16th Innovations in Theoretical Computer Science Conference</i>.
    Vol 325. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href="https://doi.org/10.4230/LIPIcs.ITCS.2025.82">10.4230/LIPIcs.ITCS.2025.82</a>'
  apa: 'Resch, N., Yuan, C., &#38; Zhang, Y. (2025). Tight bounds on list-decodable
    and list-recoverable zero-rate codes. In <i>16th Innovations in Theoretical Computer
    Science Conference</i> (Vol. 325). New York, NY, United States: Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.ITCS.2025.82">https://doi.org/10.4230/LIPIcs.ITCS.2025.82</a>'
  chicago: Resch, Nicolas, Chen Yuan, and Yihan Zhang. “Tight Bounds on List-Decodable
    and List-Recoverable Zero-Rate Codes.” In <i>16th Innovations in Theoretical Computer
    Science Conference</i>, Vol. 325. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2025. <a href="https://doi.org/10.4230/LIPIcs.ITCS.2025.82">https://doi.org/10.4230/LIPIcs.ITCS.2025.82</a>.
  ieee: N. Resch, C. Yuan, and Y. Zhang, “Tight bounds on list-decodable and list-recoverable
    zero-rate codes,” in <i>16th Innovations in Theoretical Computer Science Conference</i>,
    New York, NY, United States, 2025, vol. 325.
  ista: 'Resch N, Yuan C, Zhang Y. 2025. Tight bounds on list-decodable and list-recoverable
    zero-rate codes. 16th Innovations in Theoretical Computer Science Conference.
    ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 325, 82.'
  mla: Resch, Nicolas, et al. “Tight Bounds on List-Decodable and List-Recoverable
    Zero-Rate Codes.” <i>16th Innovations in Theoretical Computer Science Conference</i>,
    vol. 325, 82, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a
    href="https://doi.org/10.4230/LIPIcs.ITCS.2025.82">10.4230/LIPIcs.ITCS.2025.82</a>.
  short: N. Resch, C. Yuan, Y. Zhang, in:, 16th Innovations in Theoretical Computer
    Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
conference:
  end_date: 2025-01-10
  location: New York, NY, United States
  name: 'ITCS: Innovations in Theoretical Computer Science'
  start_date: 2025-01-07
corr_author: '1'
date_created: 2025-03-02T23:01:53Z
date_published: 2025-02-11T00:00:00Z
date_updated: 2025-09-30T10:42:35Z
day: '11'
ddc:
- '510'
- '000'
department:
- _id: MaMo
doi: 10.4230/LIPIcs.ITCS.2025.82
external_id:
  arxiv:
  - '2309.01800'
  isi:
  - '001532717300082'
file:
- access_level: open_access
  checksum: df3921ddf1b360b07f43d427fea51242
  content_type: application/pdf
  creator: dernst
  date_created: 2025-03-04T09:35:57Z
  date_updated: 2025-03-04T09:35:57Z
  file_id: '19286'
  file_name: 2025_LIPIcs_Resch.pdf
  file_size: 898601
  relation: main_file
  success: 1
file_date_updated: 2025-03-04T09:35:57Z
has_accepted_license: '1'
intvolume: '       325'
isi: 1
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
publication: 16th Innovations in Theoretical Computer Science Conference
publication_identifier:
  isbn:
  - '9783959773614'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Tight bounds on list-decodable and list-recoverable zero-rate codes
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 325
year: '2025'
...