Revisiting zero-rate bounds on the reliability function of discrete memoryless channels
Lists
Only you see this
Abstract
We revise the proof of low-rate upper bounds on the reliability function of discrete memoryless channels for ordinary and list-decoding schemes, in particular Berlekamp and Blinovsky's zero-rate bound, as well as Blahut's bound for low rates. The available proofs of the zero-rate bound devised by Berlekamp and Blinovsky are somehow complicated in that they contain in one form or another some cumbersome "non-standard" procedures or computations. Here we follow Blinovsky's idea of using a Ramsey-theoretic result by Komlos, and we complement it with some missing steps to present a proof which is rigorous and easier to inspect. Furthermore, we show how these techniques can be used to fix an error that invalidated the proof of Blahut's low-rate bound, which is here presented in an extended form for list decoding and for general channels.
BibTeX
@inproceedings{bondaschi2020revisiting,
author = {Marco Bondaschi and Marco Dalai},
title = {{Revisiting zero-rate bounds on the reliability function of discrete memoryless channels}},
booktitle = {ISIT},
year = {2020},
doi = {10.1109/isit44484.2020.9174491},
}| Zero-rate reliability function for mismatched decoding | IEEE Trans. Information Theory · 2022 |
| Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery | ICALP · 2023 |
| Bounds on the Zero-Error List-Decoding Capacity of the q/(q-1) Channel | ISIT · 2018 |
| Tight Bounds on List-Decodable and List-Recoverable Zero-Rate Codes | Itcs · 2025 |
| Combinatorial Bounds for List Recovery via Discrete Brascamp-Lieb Inequalities | arXiv · 2025 |
| Generalized List Decoding | Itcs · 2020 |