Near-Optimal Strong Dispersers, Erasure List-Decodable Codes and Friends

摘要

A code is (1 ? L ) erasure list-decodable if for every codeword w , after erasing any 1 ? fraction of the symbols of w , the remaining -fraction of its symbols have at most L possible completions into codewords of . Non-explicitly, there exist binary (1 ? L ) erasure list-decodable codes having rate O ( ) and tiny list-size L = O ( log 1 ) . Achieving either of these parameters explicitly is a natural open problem and was brought up in several works (e.g., [GI02,Gur03,Gur04]). While partial progress on the problem has been achieved, no explicit construction up to this work achieved rate better than ( 2 ) or list-size smaller than (1 ) (for small enough). Furthermore, Guruswami showed that no linear code can have list-size small than (1 ) [Gur03]. In this work we construct an explicit binary (1 ? L ) erasure list-decodable code having rate 1+ (for any constant 0" 0 and small enough) and list-size pol y ( log 1 ) , answering simultaneously both questions, and exhibiting an explicit non-linear code that provably beats the best possible linear one.The binary erasure list-decoding problem is equivalent to the construction of explicit, low-error, strong dispersers outputting one bit with minimal entropy-loss and seed-length. Specifically, such dispersers with error have an unavoidable entropy-loss of log log 1 and seed-length at least log 1 . Similarly to the situation with erasure list-decodable codes, no explicit construction achieved seed-length better than 2 log 1 or entropy-loss smaller than 2 log 1 , which are the best possible parameters for extractors. For every constant 0" 0 and every small , we explicitly construct an -error one-bit strong disperser with near-optimal seed-length (1 + ) log 1 and near-optimal entropy-loss O ( log log 1 ) . The main ingredient in our construction is a new (and almost-optimal) unbalanced two-source extractor. The extractor extracts one bit with constant error from two independent sources, where one source has length n and tiny min-entropy O ( log log n ) and the other source has length O ( log n ) and arbitrarily small constant min-entropy rate. When instantiated as a balanced two-source extractor, it improves upon Raz’s extractor [Raz05] 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 [Li15, CZ16, Coh16]) from achieving the above results.