Name
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 under- standing what pseudorandom objects it can produce. We show that every cyclic code with sufficient distance yields extractors that fool all linear tests. Furt her, we show that every polynomial code with sufficient distance yields extractors that fool all low-deg ree prediction tests. These are the first results that apply to univariate (rather than multivariate) polyno mial 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 re- stricted classes of tests. In particular, we obtain PRGs foo ling all linear tests (which amounts to a construction of �-biased spaces), and we obtain PRGs fooling all low-degree prediction tests. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11944836_12 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | Field | DocType |
unconditional prgs,certain error-correcting code,results amount,low-degree prediction test,linear test,reed-solomon code,underlying construction,cyclic code,polynomial code,sufficient distance yields extractor | Discrete mathematics,Pseudorandomness,Polynomial code,Cyclic code,Algorithm,Reed–Solomon error correction,Error detection and correction,Linear code,Random number generation,Mathematics,Pseudorandom number generator | Journal |
Volume | Issue | ISSN |
13 | 128 | 0302-9743 |
ISBN | Citations | PageRank |
3-540-49994-6 | 3 | 0.50 |
References | Authors | |
51 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shankar Kalyanaraman | 1 | 20 | 2.52 |
| Christopher Umans | 2 | 879 | 55.36 |