Goldreich, Oded ;
Viola, Emanuele ;
Wigderson, Avi
On Randomness Extraction in AC0
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 minentropy 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 <=e n/\log^(omega(1))(n), we show that AC0extraction is possible if and only if m/r <= 1+ poly(log(n)) * k/n; that is, the extraction rate m/r exceeds the trivial rate (of one) by an additive amount that is proportional to the minentropy rate k/n. In particular, nontrivial AC0extraction (i.e., m >= r+1) is possible if and only if k * r > n/poly(log(n)). For k >= n/log^(O(1))(n),
we show that AC0extraction 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/poly(n). The impossibility result is for (possibly) nonuniform AC0, whereas the possibility result hold for uniform AC0. All our impossibility results hold even for the model of bitfixing sources, where k coincides with the number of nonfixed (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 poly(1/delta) independent sources that are each of minentropy rate delta; and four sources suffice for delta=0.99. Also, we give nonexplicit AC0 extractors for bitfixing sources of entropy rate 1/poly(log(n)) (i.e., having n/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.
BibTeX  Entry
@InProceedings{goldreich_et_al:LIPIcs:2015:5051,
author = {Oded Goldreich and Emanuele Viola and Avi Wigderson},
title = {{On Randomness Extraction in AC0}},
booktitle = {30th Conference on Computational Complexity (CCC 2015)},
pages = {601668},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897811},
ISSN = {18688969},
year = {2015},
volume = {33},
editor = {David Zuckerman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5051},
URN = {urn:nbn:de:0030drops50515},
doi = {10.4230/LIPIcs.CCC.2015.601},
annote = {Keywords: AC0, randomness extractors, general minentropy sources, block sources, bitfixing sources, multiplesource extraction}
}
2015
Keywords: 

AC0, randomness extractors, general minentropy sources, block sources, bitfixing sources, multiplesource extraction 
Seminar: 

30th Conference on Computational Complexity (CCC 2015)

Issue date: 

2015 
Date of publication: 

2015 