Bondaschi, MarcoDalai, Marco2022-05-092022-05-092022-05-092022-05-0110.1109/TIT.2022.3145318https://infoscience.epfl.ch/handle/20.500.14299/187632WOS:000784190500006We 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 "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.Computer Science, Information SystemsEngineering, Electrical & ElectronicComputer ScienceEngineeringerror exponentslist decodingramsey theoryzero error capacityprobabilitytext::journal::journal article::research article