When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.9
URN: urn:nbn:de:0030-drops-126126
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12612/
 Go to the corresponding LIPIcs Volume Portal

Bounds for List-Decoding and List-Recovery of Random Linear Codes

 pdf-format:

Abstract

A family of error-correcting codes is list-decodable from error fraction p if, for every code in the family, the number of codewords in any Hamming ball of fractional radius p is less than some integer L that is independent of the code length. It is said to be list-recoverable for input list size π if for every sufficiently large subset of codewords (of size L or more), there is a coordinate where the codewords take more than π values. The parameter L is said to be the "list size" in either case. The capacity, i.e., the largest possible rate for these notions as the list size L β β, is known to be 1-h_q(p) for list-decoding, and 1-log_q π for list-recovery, where q is the alphabet size of the code family.
In this work, we study the list size of random linear codes for both list-decoding and list-recovery as the rate approaches capacity. We show the following claims hold with high probability over the choice of the code (below q is the alphabet size, and Ξ΅ > 0 is the gap to capacity).
- A random linear code of rate 1 - log_q(π) - Ξ΅ requires list size L β₯ π^{Ξ©(1/Ξ΅)} for list-recovery from input list size π. This is surprisingly in contrast to completely random codes, where L = O(π/Ξ΅) suffices w.h.p.
- A random linear code of rate 1 - h_q(p) - Ξ΅ requires list size L β₯ β {h_q(p)/Ξ΅+0.99}β for list-decoding from error fraction p, when Ξ΅ is sufficiently small.
- A random binary linear code of rate 1 - hβ(p) - Ξ΅ is list-decodable from average error fraction p with list size with L β€ β {hβ(p)/Ξ΅}β + 2. (The average error version measures the average Hamming distance of the codewords from the center of the Hamming ball, instead of the maximum distance as in list-decoding.)
The second and third results together precisely pin down the list sizes for binary random linear codes for both list-decoding and average-radius list-decoding to three possible values.
Our lower bounds follow by exhibiting an explicit subset of codewords so that this subset - or some symbol-wise permutation of it - lies in a random linear code with high probability. This uses a recent characterization of (Mosheiff, Resch, Ron-Zewi, Silas, Wootters, 2019) of configurations of codewords that are contained in random linear codes. Our upper bound follows from a refinement of the techniques of (Guruswami, HΓ₯stad, Sudan, Zuckerman, 2002) and strengthens a previous result of (Li, Wootters, 2018), which applied to list-decoding rather than average-radius list-decoding.

BibTeX - Entry

```@InProceedings{guruswami_et_al:LIPIcs:2020:12612,
author =	{Venkatesan Guruswami and Ray Li and Jonathan Mosheiff and Nicolas Resch and Shashwat Silas and Mary Wootters},
title =	{{Bounds for List-Decoding and List-Recovery of Random Linear Codes}},
booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages =	{9:1--9:21},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-164-1},
ISSN =	{1868-8969},
year =	{2020},
volume =	{176},
editor =	{Jaros{\l}aw Byrka and Raghu Meka},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12612},
URN =		{urn:nbn:de:0030-drops-126126},
doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.9},
annote =	{Keywords: list-decoding, list-recovery, random linear codes, coding theory}
}
```

 Keywords: list-decoding, list-recovery, random linear codes, coding theory Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) Issue Date: 2020 Date of publication: 11.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy