A Caltech Library Service

On Obtaining Pseudorandomness from Error-Correcting Codes

Kalyanaraman, Shankar and Umans, Christopher (2006) On Obtaining Pseudorandomness from Error-Correcting Codes. In: FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science. No.4337. Springer , Berlin, Heidelberg, pp. 105-116. ISBN 9783540499947.

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

Use this Persistent URL to link to this item:


A number of recent results have constructed randomness extractors and pseudorandom generators (PRGs) directly from certain error-correcting codes. The underlying construction in these results amounts to picking a random index into the codeword and outputting m consecutive symbols (the codeword is obtained from the weak random source in the case of extractors, and from a hard function in the case of PRGs). We study this construction applied to general cyclic error-correcting codes, with the goal of understanding what pseudorandom objects it can produce. We show that every cyclic code with sufficient distance yields extractors that fool all linear tests. Further, we show that every polynomial code with sufficient distance yields extractors that fool all low-degree prediction tests. These are the first results that apply to univariate (rather than multivariate) polynomial codes, hinting that Reed-Solomon codes may yield good randomness extractors. Our proof technique gives rise to a systematic way of producing unconditional PRGs against restricted classes of tests. In particular, we obtain PRGs fooling all linear tests (which amounts to a construction of ε-biased spaces), and we obtain PRGs fooling all low-degree prediction tests.

Item Type:Book Section
Related URLs:
URLURL TypeDescription ItemJournal Article ReadCube access
Additional Information:© Springer-Verlag Berlin Heidelberg 2006. This research was supported by NSF grant CCF-0346991 and by BSF grant 2004329. We thank Eli Ben-Sasson for helpful discussions and Andrej Bogdanov for sharing a draft of [Bog05] with us.We also thank the anonymous referees for their insightful comments.
Funding AgencyGrant Number
Binational Science Foundation (USA-Israel)2004329
Subject Keywords:Success Probability; Linear Code; Cyclic Code; Prediction Test; Linear Test
Series Name:Lecture Notes in Computer Science
Issue or Number:4337
Record Number:CaltechAUTHORS:20190828-102318013
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98302
Deposited By: George Porter
Deposited On:28 Aug 2019 17:55
Last Modified:16 Nov 2021 17:38

Repository Staff Only: item control page