CaltechAUTHORS
  A Caltech Library Service

Better Condensers and New Extractors from Parvaresh-Vardy Codes

Ta-Shma, Amnon and Umans, Christopher (2012) Better Condensers and New Extractors from Parvaresh-Vardy Codes. In: 2012 IEEE 27th Conference on Computational Complexity. IEEE , Piscataway, NJ, pp. 309-315. ISBN 9780769547084. https://resolver.caltech.edu/CaltechAUTHORS:20191126-140535982

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20191126-140535982

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/ccc.2012.25DOIArticle
Additional Information:© 2012 IEEE. Amnon Ta-Shma was supported by Grant No. 2010120 from the United States-Israel Binational Science Foundation (BSF), and by Grant No. 1090/10 from the Israel Science foundation (ISF). Christopher Umans was supported by NSF CCF-0846991, CCF-1116111 and BSF grant 2010120. We thank Zeev Dvir, Ariel Gabizon, Swastik Kopparty, and Ronen Shaltiel for useful discussions. Thanks for Zeev Dvir for confirming that the extractors of [3] work with smaller ε than claimed in the paper.
Funders:
Funding AgencyGrant Number
Binational Science Foundation (USA-Israel)2010120
Israel Science Foundation1090/10
NSFCCF-0846991
NSFCCF-1116111
Subject Keywords:randomness extractors, Parvaresh-Vardy codes, condensers
DOI:10.1109/ccc.2012.25
Record Number:CaltechAUTHORS:20191126-140535982
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20191126-140535982
Official Citation:A. Ta-Shma and C. Umans, "Better Condensers and New Extractors from Parvaresh-Vardy Codes," 2012 IEEE 27th Conference on Computational Complexity, Porto, 2012, pp. 309-315. doi: 10.1109/CCC.2012.25
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:100072
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:26 Nov 2019 22:45
Last Modified:16 Nov 2021 17:51

Repository Staff Only: item control page