Better Condensers and New Extractors from Parvaresh-Vardy Codes

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Ta-Shma, A., Umans, C.
Format: Conference Proceeding
Language:English
Subjects:
condensers
Corporate acquisitions
Entropy
Frequency modulation
Interpolation
Linear systems
Parvaresh-Vardy codes
Polynomials
Radio frequency
randomness extractors
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ε ≥ 1/2 logβ n for any constant ß
ISSN:1093-0159
2575-8403
DOI:10.1109/CCC.2012.25