
In this work we consider the list-decodability and list-recoverability of arbitrary $q$-ary codes, for all integer values of $q\geq 2$. A code is called $(p,L)_q$-list-decodable if every radius $pn$ Hamming ball contains less than $L$ codewords; $(p,\ell,L)_q$-list-recoverability is a generalization where we place radius $pn$ Hamming balls on every point of a combinatorial rectangle with side length $\ell$ 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,\ell,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_*+\varepsilon$ fraction of errors must have size $O_{\varepsilon}(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_*-\varepsilon$ 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.
FOS: Computer and information sciences, \(q\)-ary code, Combinatorial codes, List-decoding, Decoding, Computer Science - Information Theory, Information Theory (cs.IT), list-decodability, Computational Complexity (cs.CC), Zero-rate thresholds, 004, List-recovery, Computer Science - Computational Complexity, FOS: Mathematics, Mathematics - Combinatorics, Coding theory, Combinatorics (math.CO), list-recoverability, ddc: ddc:004
FOS: Computer and information sciences, \(q\)-ary code, Combinatorial codes, List-decoding, Decoding, Computer Science - Information Theory, Information Theory (cs.IT), list-decodability, Computational Complexity (cs.CC), Zero-rate thresholds, 004, List-recovery, Computer Science - Computational Complexity, FOS: Mathematics, Mathematics - Combinatorics, Coding theory, Combinatorics (math.CO), list-recoverability, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
