Near-Optimal Erasure List-Decodable Codes

For every small ?, we explicitly construct binary erasure list-decodable codes that can be list-decoded from 1-? fraction of erasures, with near-optimal list-size poly(log(1/?)) and near-optimal rate O(?^(1+?)) where ?>0 is any constant. This is the first construction to break the ?^2 rate barrier, solving a long-standing open problem raised by Guruswami and Indyk, and it does so with a remarkably small list size (we remark that Guruswami showed such a result is impossible using linear codes, and indeed our code is not linear). Equivalently, in terms of dispersers, we construct ?-error one-bit strong dispersers with near-optimal seed-length and near-optimal entropy-loss. The main ingredient in the construction is a new (and nearly 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(loglog n) and the other source has length O(log n) and arbitrarily small constant min-entropy rate. Joint work with Avraham Ben-Aroya and Amnon Ta-Shma.