Extractors and condensers from univariate polynomials

Abstract: We give new constructions of randomness extractors and lossless condensers that are optimal to within constant factors in both the seed length and the output length. For extractors, this matches the parameters of the current best known construction [LRVW03]; for lossless condensers, the previous best constructions achieved optimality to within a constant factor in one parameter only at the expense of a polynomial loss in the other. Most significantly, our constructions are all simple to describe, and they have short and self-contained algebraic analyses. The constructions are based on the Parvaresh-Vardy codes, and our proof technique is new, inspired by the list- decoding algorithm for those codes. This is joint work with Venkat Guruswami and Salil Vadhan.