On Randomness Extraction in AC0
On Randomness Extraction in AC0
复制标题
关于AC0中的随机性提取
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
A. Wigderson
中科院分区：
文献类型：
--
作者：
Oded Goldreich;Emanuele Viola;A. Wigderson
我们考虑通过 AC0 电路进行随机性提取。主要参数 n 是源的长度，所有其他参数都是它的函数。附加提取参数是最小熵界限 k = k(n)、种子长度 r = r(n)、输出长度 m = m(n) 和（输出）偏差界限 e = e(n)。
对于 k ≤ n/logω(1) n，我们证明当且仅当 m/r ≤ 1+poly(log n)· k/n 时，AC0 提取是可能的；也就是说，提取率 m/r 超过平凡率 (1) 与最小熵率 k/n 成比例的添加量。特别是，当且仅当 k · r > n/poly(log n) 时，非平凡的 AC0 提取（即 m ≥ r + 1）才是可能的。对于 k ≥ n/logO(1) n，我们表明，当 r = O(log n) 时，AC0 提取 r + Ω(r) 位是可能的，但在这种情况下是否可以提取更多位的问题仍悬而未决。
不可能结果针对常数 e，可能性结果支持 e = 1/poly(n)。不可能结果适用于（可能）非均匀 AC0，而可能性结果适用于均匀 AC0。即使对于位固定源模型，我们所有的不可能性结果也成立，其中 k 与非固定（即随机）位的数量一致。
我们还考虑从各类受限源中进行确定性 AC0 提取。特别是，对于任何常数 δ > 0，我们为 Poly(1/δ) 独立源给出显式 AC0 提取器，每个源都是最小熵率 δ；四个来源足以使 δ = 0.99。此外，我们还为熵率为 1/poly(log n) 的位固定源提供非显式 AC0 提取器（即，具有 n/poly(log n) 未固定位）。这表明，即使根据电路确定性地选择限制，“限制方法”（通过固定尽可能少的变量使电路恒定）的已知分析对于 AC0 来说也是严格的。
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 e = e(n).
For k ≤ n/logω(1) n, we show that AC0-extraction 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 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 e, and the possibility result supports e = 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.
We also consider deterministic AC0 extraction from various classes of restricted sources. In particular, for any constant δ > 0, we give explicit AC0 extractors for poly(1/δ) independent sources that are each of min-entropy rate δ; and four sources suffice for δ = 0.99. Also, we give non-explicit AC0 extractors for bit-fixing 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.