Better Condensers and New Extractors from Parvaresh-Vardy Codes

Abstract

We give a new construction of condensers based on Parvaresh-Vardy codes [1]. Our condensers have entropy rate (1-α) for subconstant α (in contrast to [2] which required constant α) and suffer only sublinear entropy loss. Known extractors can be applied to the output to extract all but a subconstant fraction of the minentropy. The resulting (k, ε) extractor E : {0, 1}^n × {0, 1}^d → {0, 1}^m has output length m = (1- α)k with α = 1/poly log(n), and seed length d = O(log n), when ε ≥ ½^(logβ n) for any constant ß < 1. Thus we achieve the same "world-record" extractor parameters as [3], with a more direct construction.

Additional details