---
res:
  bibo_abstract:
  - "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,\U0001D4C1,L)_q-list-recoverability
    is a generalization where we place radius pn Hamming balls on every point of a
    combinatorial rectangle with side length \U0001D4C1 and again stipulate that there
    be less than L codewords.\r\nOur main contribution is to precisely calculate the
    maximum value of p for which there exist infinite families of positive rate (p,\U0001D4C1,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.\r\nTechnically, 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.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Nicolas
      foaf_name: Resch, Nicolas
      foaf_surname: Resch
  - foaf_Person:
      foaf_givenName: Chen
      foaf_name: Yuan, Chen
      foaf_surname: Yuan
  - foaf_Person:
      foaf_givenName: Yihan
      foaf_name: Zhang, Yihan
      foaf_surname: Zhang
      foaf_workInfoHomepage: http://www.librecat.org/personId=2ce5da42-b2ea-11eb-bba5-9f264e9d002c
    orcid: 0000-0002-6465-6258
  bibo_doi: 10.4230/LIPIcs.ICALP.2023.99
  bibo_volume: 261
  dct_date: 2023^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1868-8969
  - http://id.crossref.org/issn/9783959772785
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_title: Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery@
...