2026-07-21T23:54:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11736 2024-03-06T10:48:35Z ddc:004 open_access

Generalized List Decoding Zhang, Yihan Budkuley, Amitalok J. Jaggi, Sidharth Generalized Plotkin bound general adversarial channels equicoupled codes random coding completely positive tensors copositive tensors hypergraph Ramsey theory This paper concerns itself with the question of list decoding for general adversarial channels, e.g., bit-flip (XOR) channels, erasure channels, AND (Z-) channels, OR channels, real adder channels, noisy typewriter channels, etc. We precisely characterize when exponential-sized (or positive rate) (L-1)-list decodable codes (where the list size L is a universal constant) exist for such channels. Our criterion essentially asserts that: For any given general adversarial channel, it is possible to construct positive rate (L-1)-list decodable codes if and only if the set of completely positive tensors of order-L with admissible marginals is not entirely contained in the order-L confusability set associated to the channel. The sufficiency is shown via random code construction (combined with expurgation or time-sharing). The necessity is shown by 1) extracting approximately equicoupled subcodes (generalization of equidistant codes) from any using hypergraph Ramsey’s theorem, and 2) significantly extending the classic Plotkin bound in coding theory to list decoding for general channels using duality between the completely positive tensor cone and the copositive tensor cone. In the proof, we also obtain a new fact regarding asymmetry of joint distributions, which may be of independent interest. Other results include 1) List decoding capacity with asymptotically large L for general adversarial channels; 2) A tight list size bound for most constant composition codes (generalization of constant weight codes); 3) Rederivation and demystification of Blinovsky’s [Blinovsky, 1986] characterization of the list decoding Plotkin points (threshold at which large codes are impossible) for bit-flip channels; 4) Evaluation of general bounds [Wang et al., 2019] for unique decoding in the error correction code setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yihan Zhang and Amitalok J. Budkuley and Sidharth Jaggi 2020 Is Part Of LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2020.51 urn:nbn:de:0030-drops-117368 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.51 eng https://creativecommons.org/licenses/by/3.0/legalcode