Better Condensers and New Extractors from Parvaresh-Vardy Codes
Amnon Ta‐Shma, Christopher Umans · 2012
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}mhas output length m = (1- α)k with α = 1/poly log(n), and seed length d = O(log n), when ε ≥ 1/2logβn for any constant ß <; 1. Thus we achieve the same “world-record” extractor parameters as [3], with a more direct construction.