On Randomness Extraction in AC0

Webpage for a paper by Goldreich, Viola, and Wigderson


Abstract

We consider randomness extraction by AC0 circuits. The main parameter, $n$, is the length of the source, and all other parameters are functions of it. The additional extraction parameters are the min-entropy bound $k=k(n)$, the seed length $r=r(n)$, the output length $m=m(n)$, and the (output) deviation bound $\epsilon=\epsilon(n)$.

For $k \le n/\log^{\omega(1)}n$, we show that AC0-extraction is possible if and only if $\frac{m}{r}\leq 1+{\rm poly}(\log n)\cdot\frac{k}{n}$; that is, the extraction rate $m/r$ exceeds the trivial rate (of one) by an additive amount that is proportional to the min-entropy rate $k/n$. In particular, non-trivial AC0-extraction (i.e., $m\geq r+1$) is possible if and only if $k\cdot r>n/{\rm poly}(\log n)$. For $k \ge n/\log^{O(1)} n$, we show that AC0-extraction of $r+\Omega(r)$ bits is possible when $r=O(\log n)$, but leave open the question of whether more bits can be extracted in this case.

The impossibility result is for constant $\epsilon$, and the possibility result supports $\epsilon=1/{\rm poly}(n)$. The impossibility result is for (possibly) non-uniform AC0, whereas the possibility result hold for uniform AC0. All our impossibility results hold even for the model of bit-fixing sources, where $k$ coincides with the number of non-fixed (i.e., random) bits.

We also consider deterministic AC0 extraction from various classes of restricted sources. In particular, for any constant $\delta>0$, we give explicit AC0 extractors for ${\rm poly}(1/\delta)$ independent sources that are each of min-entropy rate~$\delta$; and four sources suffice for $\delta=0.99$. Also, we give non-explicit AC0 extractors for bit-fixing sources of entropy rate $1/{\rm poly}(\log n)$ (i.e., having $n/{\rm poly}(\log n)$ unfixed bits). This shows that the known analysis of the ``restriction method'' (for making a circuit constant by fixing as few variables as possible) is tight for AC0 even if the restriction is picked deterministically depending on the circuit.

Material available on-line


Back to either Oded Goldreich's homepage or general list of papers.