---
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@
...