Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy
Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy
复制标题
改进的双源提取器和多对数熵仿射提取器
DOI：
10.1109/focs.2016.26
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Xin Li
中科院分区：
文献类型：
--
作者：
Xin Li
在最近的一项突破 [1] 中，Chattopadhyay 和 Zuckerman 给出了一个显式的双源提取器，对于某个足够大的常数 C，最小熵 k ≥ logC n ，其中 n 是源的长度。然而，他们的提取器只输出一位。在本文中，我们将双源提取器的输出提高到 kΩ(1)，而误差仍然是 n-Ω(1)，并且提取器在第二个源中仍然很强。在非强的情况下，输出可以增加到k。我们的改进是通过为 (q, t, γ) 非遗忘位固定源提供更好的提取器来实现的，它可以输出 tΩ(1) 位而不是[1]中的一位。我们还给出了 F2 上仿射源的确定性提取器的第一个显式构造，其中对于某个足够大的常数 C，熵 k ≥ logC n，其中 n 是源的长度。此前最著名的结果是 Bourgain [2]、Yehudayoff [3] 和 Li [4] 的结果，它们要求仿射源的熵至少为 Ω(n/√log log n)。我们的提取器输出 kΩ(1) 位，误差为 n-Ω(1)。这是通过将仿射源减少为非遗忘位固定源来完成的，其中我们将之前关于独立源提取器 [5] 的工作中基于交替提取的方法调整为仿射设置。我们的仿射提取器还意味着对[6]中研究的电路源的提取器进行了改进。我们进一步将我们的结果扩展到零误差分散器的情况，并给出了数据结构中的两个应用，这些应用主要依赖于我们的双源或仿射提取器具有大输出大小的事实。
In a recent breakthrough [1], Chattopadhyay and Zuckerman gave an explicit two-source extractor for min-entropy k ≥ logC n for some large enough constant C, where n is the length of the source. However, their extractor only outputs one bit. In this paper, we improve the output of the two-source extractor to kΩ(1), while the error remains n-Ω(1) and the extractor remains strong in the second source. In the non-strong case, the output can be increased to k. Our improvement is obtained by giving a better extractor for (q, t, γ) non-oblivious bit-fixing sources, which can output tΩ(1) bits instead of one bit as in [1]. We also give the first explicit construction of deterministic extractors for affine sources over F2, with entropy k ≥ logC n for some large enough constant C, where n is the length of the source. Previously the best known results are by Bourgain [2], Yehudayoff [3] and Li [4], which require the affine source to have entropy at least Ω(n/√log log n). Our extractor outputs kΩ(1) bits with error n-Ω(1). This is done by reducing an affine source to a non-oblivious bit-fixing source, where we adapt the alternating extraction based approach in previous work on independent source extractors [5] to the affine setting. Our affine extractors also imply improved extractors for circuit sources studied in [6]. We further extend our results to the case of zero-error dispersers, and give two applications in data structures that rely crucially on the fact that our two-source or affine extractors have large output size.
影响因子：
4.9
作者：
Chattopadhyay, Eshan;Zuckerman, David
通讯作者：
Zuckerman, David