Abstract
A family of errorcorrecting codes is listdecodable 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 listrecoverable 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 1h_q(p) for listdecoding, and 1log_q ? for listrecovery, where q is the alphabet size of the code family.
In this work, we study the list size of random linear codes for both listdecoding and listrecovery 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 listrecovery 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 listdecoding from error fraction p, when ε is sufficiently small.
 A random binary linear code of rate 1  h₂(p)  ε is listdecodable 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 listdecoding.)
The second and third results together precisely pin down the list sizes for binary random linear codes for both listdecoding and averageradius listdecoding to three possible values.
Our lower bounds follow by exhibiting an explicit subset of codewords so that this subset  or some symbolwise permutation of it  lies in a random linear code with high probability. This uses a recent characterization of (Mosheiff, Resch, RonZewi, 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 listdecoding rather than averageradius listdecoding.
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 ListDecoding and ListRecovery of Random Linear Codes}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {9:19:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771641},
ISSN = {18688969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12612},
URN = {urn:nbn:de:0030drops126126},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.9},
annote = {Keywords: listdecoding, listrecovery, random linear codes, coding theory}
}
Keywords: 

listdecoding, listrecovery, 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 