Revisiting Zero-Rate Bounds on the Reliability Function of Discrete Memoryless Channels
Lists
Only you see this
Abstract
We present a revised proof of Berlekamp's zero-rate upper bound on the reliability function of discrete memoryless channels, in its extended form for list-decoding as first proved by Blinovsky. The available proofs are somehow uneasy in that they contain in one form or another some cumbersome "nonstandard" procedures or computations. Here we start from Blinovsky's ideas and complement them with some missing steps to present a proof which is entirely in the realm of standard information theoretic tools even for general list size.
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 |