ECCC-Report TR15-003https://eccc.weizmann.ac.il/report/2015/003Comments and Revisions published for TR15-003en-usSat, 03 Jan 2015 15:29:26 +0200
Paper TR15-003
| On Randomness Extraction in AC0 |
Oded Goldreich,
Emanuele Viola,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2015/003We 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.
Sat, 03 Jan 2015 15:29:26 +0200https://eccc.weizmann.ac.il/report/2015/003