## 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.