List-Decoding Capacity Implies Capacity on the 𝑞�-ary Symmetric Channel

Abstract

It is known that the Shannon capacity of the q-ary symmetric channel (qSC) is the same as the list-decoding capacity of an adversarial channel, raising the question of whether there is a formal (and black-box) connection between the two. We show that there is: Any linear code C⊆ Fqn that has superconstant minimum distance and achieves list-decoding capacity also achieves capacity on the qSC.