Name
Abstract | ||
|---|---|---|
This paper studies combinatorial properties of codes for the Z-channel. A Z-channel with error fraction τ takes as input a length-n binary codeword and injects in an adversarial manner up to nτ asymmetric errors, i.e., errors that only zero out bits but do not flip 0’s to 1’s. It is known that the largest (L − 1)-list-decodable code for the Z-channel with error fraction τ has exponential (in n) size if τ is less than a critical value that we call the Plotkin point and has constant size if τ is larger than the threshold. The (L−1)-list-decoding Plotkin point is known to be ${L^{ - \frac{1}{{L - 1}}}} - {L^{ - \frac{L}{{L - 1}}}}$. In this paper, we show that the largest (L−1)-list-decodable code ε-above the Plotkin point has size Θ
<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">L</inf>
(ε
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">−3/2</sup>
) for any L − 1 ≥ 1. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1109/ISIT50566.2022.9834829 | 2022 IEEE International Symposium on Information Theory (ISIT) |
Keywords | DocType | ISSN |
list-decodable zero-rate codes,Z-channel,error fraction τ,length-n binary codeword,injects,adversarial manner,asymmetric errors,L - 1,largest-list-decodable code ε-above | Conference | 2157-8095 |
ISBN | Citations | PageRank |
978-1-6654-2160-7 | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nikita Polyanskii | 1 | 0 | 0.34 |
| Yihan Zhang | 2 | 0 | 0.68 |