License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.99
URN: urn:nbn:de:0030-drops-181518
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18151/
Resch, Nicolas ;
Yuan, Chen ;
Zhang, Yihan
Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery
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,?,L)_q-list-recoverability is a generalization where we place radius pn Hamming balls on every point of a combinatorial rectangle with side length ? 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,?,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.
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.
BibTeX - Entry
@InProceedings{resch_et_al:LIPIcs.ICALP.2023.99,
author = {Resch, Nicolas and Yuan, Chen and Zhang, Yihan},
title = {{Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {99:1--99:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-278-5},
ISSN = {1868-8969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18151},
URN = {urn:nbn:de:0030-drops-181518},
doi = {10.4230/LIPIcs.ICALP.2023.99},
annote = {Keywords: Coding theory, List-decoding, List-recovery, Zero-rate thresholds}
}
|
Keywords: |
|
Coding theory, List-decoding, List-recovery, Zero-rate thresholds |
|
Collection: |
|
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
05.07.2023 |
