ACM Symposium on Theory of Computing (STOC)
List-Decoding Capacity Implies Capacity on the 𝑞-ary Symmetric Channel
Francisco Pernice, Oscar Sprumont, Mary K. Wootters
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 𝐶 ⊆ F 𝑛 𝑞 that has superconstant minimum distance and achieves list-decoding capacity also achieves capacity on the qSC. CCS Concepts• Theory of computation → Error-correcting codes.