Abstract
A code ? ⊆ {0,1}^n̅ is (s,L) erasure listdecodable if for every word w, after erasing any s symbols of w, the remaining n̅s symbols have at most L possible completions into a codeword of ?. Nonexplicitly, there exist binary ((1τ)n̅,L) erasure listdecodable codes with rate approaching τ and tiny listsize L = O(log 1/(τ)). Achieving either of these parameters explicitly is a natural open problem (see, e.g., [Guruswami and Indyk, 2002; Guruswami, 2003; Guruswami, 2004]). While partial progress on the problem has been achieved, no prior nontrivial explicit construction achieved rate better than Ω(τ²) or listsize smaller than Ω(1/τ). Furthermore, Guruswami showed no linear code can have listsize smaller than Ω(1/τ) [Guruswami, 2003]. We construct an explicit binary ((1τ)n̅,L) erasure listdecodable code having rate τ^(1+γ) (for any constant γ > 0 and small τ) and listsize poly(log 1/τ), answering simultaneously both questions, and exhibiting an explicit nonlinear code that provably beats the best possible linear code.
The binary erasure listdecoding problem is equivalent to the construction of explicit, lowerror, strong dispersers outputting one bit with minimal entropyloss and seedlength. For error ε, no prior explicit construction achieved seedlength better than 2log(1/ε) or entropyloss smaller than 2log(1/ε), which are the best possible parameters for extractors. We explicitly construct an εerror onebit strong disperser with nearoptimal seedlength (1+γ)log(1/ε) and entropyloss O(log log1/ε).
The main ingredient in our construction is a new (and almostoptimal) unbalanced twosource extractor. The extractor extracts one bit with constant error from two independent sources, where one source has length n and tiny minentropy O(log log n) and the other source has length O(log n) and arbitrarily small constant minentropy rate. When instantiated as a balanced twosource extractor, it improves upon Raz’s extractor [Raz, 2005] in the constant error regime. The construction incorporates recent components and ideas from extractor theory with a delicate and novel analysis needed in order to solve dependency and error issues that prevented previous papers (such as [Li, 2015; Chattopadhyay and Zuckerman, 2019; Cohen, 2016]) from achieving the above results.
BibTeX  Entry
@InProceedings{benaroya_et_al:LIPIcs:2020:12553,
author = {Avraham BenAroya and Dean Doron and Amnon TaShma},
title = {{NearOptimal Erasure ListDecodable Codes}},
booktitle = {35th Computational Complexity Conference (CCC 2020)},
pages = {1:11:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771566},
ISSN = {18688969},
year = {2020},
volume = {169},
editor = {Shubhangi Saraf},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12553},
URN = {urn:nbn:de:0030drops125531},
doi = {10.4230/LIPIcs.CCC.2020.1},
annote = {Keywords: Dispersers, Erasure codes, List decoding, Ramsey graphs, Twosource extractors}
}
Keywords: 

Dispersers, Erasure codes, List decoding, Ramsey graphs, Twosource extractors 
Collection: 

35th Computational Complexity Conference (CCC 2020) 
Issue Date: 

2020 
Date of publication: 

17.07.2020 