Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-128 | 5th October 2006 00:00

On obtaining pseudorandomness from error-correcting codes.


Authors: Shankar Kalyanaraman, Chris Umans
Publication: 9th October 2006 12:47
Downloads: 3123


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 {\em every}
cyclic code with sufficient distance yields extractors that fool
all linear tests. Further, we show that {\em 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

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.

ISSN 1433-8092 | Imprint