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 {\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 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.