License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.51
URN: urn:nbn:de:0030-drops-117368
Go to the corresponding LIPIcs Volume Portal

Zhang, Yihan ; Budkuley, Amitalok J. ; Jaggi, Sidharth

Generalized List Decoding

LIPIcs-ITCS-2020-51.pdf (1 MB)


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.

BibTeX - Entry

  author =	{Yihan Zhang and Amitalok J. Budkuley and Sidharth Jaggi},
  title =	{{Generalized List Decoding}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{51:1--51:83},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Thomas Vidick},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-117368},
  doi =		{10.4230/LIPIcs.ITCS.2020.51},
  annote =	{Keywords: Generalized Plotkin bound, general adversarial channels, equicoupled codes, random coding, completely positive tensors, copositive tensors, hypergrap}

Keywords: Generalized Plotkin bound, general adversarial channels, equicoupled codes, random coding, completely positive tensors, copositive tensors, hypergrap
Collection: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Issue Date: 2020
Date of publication: 06.01.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI