Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-003 | 3rd January 2015 15:28

On Randomness Extraction in AC0


Authors: Oded Goldreich, Emanuele Viola, Avi Wigderson
Publication: 3rd January 2015 15:29
Downloads: 610


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.

ISSN 1433-8092 | Imprint