Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery

Authors Nicolas Resch, Chen Yuan, Yihan Zhang

Publication date 14 October 2022

Abstract: In this work we consider the list-decodability and list-recoverability of arbitrary

q

-ary codes, for all integer values of

q g e q 2

. A code is called

(p, L)_{q}

-list-decodable if every radius

p n

Hamming ball contains less than

L

codewords;

(p, e l l, L)_{q}

-list-recoverability is a generalization where we place radius

p n

Hamming balls on every point of a combinatorial rectangle with side length

e l l

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, e l l, 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_{*} + v a r e p s i l o n

fraction of errors must have size

O_{v a r e p s i l o n} (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_{*} - v a r e p s i l o n$ 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.

This page was built for publication: Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6413939)