Kalyanaraman, Shankar and Umans, Christopher (2006) On obtaining pseudorandomness from error-correcting codes. Electronic Colloquium on Computational Complexity, 2006 . TR06-128. ISSN 1433-8092. https://resolver.caltech.edu/CaltechAUTHORS:20190829-152850467
![]() |
PDF
- Published Version
See Usage Policy. 145kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190829-152850467
Abstract
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 epsilon-biased spaces), and we obtain PRGs fooling all low-degree prediction tests.
Item Type: | Article | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| |||||||||
Additional Information: | 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. | |||||||||
Funders: |
| |||||||||
Subject Keywords: | Coding theory, extractors, Pseudorandomness | |||||||||
Record Number: | CaltechAUTHORS:20190829-152850467 | |||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20190829-152850467 | |||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
ID Code: | 98358 | |||||||||
Collection: | CaltechAUTHORS | |||||||||
Deposited By: | George Porter | |||||||||
Deposited On: | 30 Aug 2019 14:18 | |||||||||
Last Modified: | 03 Oct 2019 21:40 |
Repository Staff Only: item control page