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.APPROX-RANDOM.2018.50
URN: urn:nbn:de:0030-drops-94547
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9454/
Go to the corresponding LIPIcs Volume Portal

Li, Ray ; Wootters, Mary

Improved List-Decodability of Random Linear Binary Codes

pdf-format:
LIPIcs-APPROX-RANDOM-2018-50.pdf (0.5 MB)

Abstract

There has been a great deal of work establishing that random linear codes are as list-decodable as uniformly random codes, in the sense that a random linear binary code of rate 1 - H(p) - epsilon is (p,O(1/epsilon))-list-decodable with high probability. In this work, we show that such codes are (p, H(p)/epsilon + 2)-list-decodable with high probability, for any p in (0, 1/2) and epsilon > 0. In addition to improving the constant in known list-size bounds, our argument - which is quite simple - works simultaneously for all values of p, while previous works obtaining L = O(1/epsilon) patched together different arguments to cover different parameter regimes.
Our approach is to strengthen an existential argument of (Guruswami, Håstad, Sudan and Zuckerman, IEEE Trans. IT, 2002) to hold with high probability. To complement our upper bound for random linear binary codes, we also improve an argument of (Guruswami, Narayanan, IEEE Trans. IT, 2014) to obtain a tight lower bound of 1/epsilon on the list size of uniformly random binary codes; this implies that random linear binary codes are in fact more list-decodable than uniformly random binary codes, in the sense that the list sizes are strictly smaller.
To demonstrate the applicability of these techniques, we use them to (a) obtain more information about the distribution of list sizes of random linear binary codes and (b) to prove a similar result for random linear rank-metric codes.

BibTeX - Entry

@InProceedings{li_et_al:LIPIcs:2018:9454,
  author =	{Ray Li and Mary Wootters},
  title =	{{Improved List-Decodability of Random Linear Binary Codes}},
  booktitle =	{Approximation, Randomization, and Combinatorial  Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{50:1--50:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9454},
  URN =		{urn:nbn:de:0030-drops-94547},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.50},
  annote =	{Keywords: List-decoding, Random linear codes, Rank-metric codes}
}

Keywords: List-decoding, Random linear codes, Rank-metric codes
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Issue Date: 2018
Date of publication: 13.08.2018

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