Loading...
Please wait, while we are loading the content...
Similar Documents
On Randomness Extraction in AC0 (2015)
| Content Provider | CiteSeerX |
|---|---|
| Author | Goldreich, Oded Viola, Emanuele Wigderson, Avi |
| 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 = (n). For k ≤ n / logω(1) n, we show that AC0-extraction is possible if and only if mr ≤ 1 + poly(log n) · kn; that is, the extraction rate m/r exceeds the trivial rate (of one) by an addi-tive amount that is proportional to the min-entropy rate k/n. In particular, non-trivial AC0-extraction (i.e., m ≥ r + 1) is possible if and only if k · r> n/poly(log n). For k ≥ n / logO(1) n, we show that AC0-extraction of r+ Ω(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 , and the possibility result supports = 1/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. |
| File Format | |
| Publisher Date | 2015-01-01 |
| Access Restriction | Open |
| Subject Keyword | Randomness Extraction Impossibility Result Non-uniform Ac0 Possibility Result Hold Possibility Result Addi-tive Amount Main Parameter Ac0 Circuit Non-trivial Ac0-extraction Output Length Min-entropy Bound Additional Extraction Parameter Bit-fixing Source Uniform Ac0 Min-entropy Rate Extraction Rate Seed Length Trivial Rate |
| Content Type | Text |
