论文标题
改进的小空间来源提取器
Improved Extractors for Small-Space Sources
论文作者
论文摘要
我们研究了从弱来源中提取随机位的问题，这些弱来源是通过记忆力有限的算法进行采样的。这种小空间来源的模型是由坎普，劳，瓦丹和扎克曼（Stoc'06）引入的，并属于Trevisan和Vadhan（focs'00）对从弱来源中提取随机性提出的一系列研究，这些研究是通过计算界限算法来取样的弱来源。我们的主要结果是以下。 1。我们在多项式误差方面获得了小空间源的近乎最佳提取器。对于$ n $ bits的太空$ s $源，我们的提取器仅需$ k \ geq s \ cdot $ polylog $（n）$熵。这是对先前最佳结果的指数改进，需要$ k \ geq s^{1.1} \ cdot2^{\ log^{0.51} n} $（Chattopadhyay and Li，stoc'16）。 2。我们在可忽略不计的误差方面获得了小空间源的提取器。对于$ n $ bits的太空$ s $源，我们的提取器需要熵$ k \ geq n^{1/2+δ} \ cdot s^{1/2-δ} $，而先前的最佳结果$ k \ geq n^{2/3+δ} stoc'20）。 为了获得我们的第一个结果，关键成分是从小空间来源降低到仿射来源的新减少，从而使我们可以简单地应用良好的仿射提取器。 为了获得第二个结果，我们必须开发一些新的机械，因为我们没有用于低熵的低错误仿期提取器。我们的主要工具是用于对抗来源的显着改进的提取器，该工具是通过简单的框架构建的，该框架通过将它们与一般类型的极端设计结合在一起，从而使某种泄漏弹性的提取器（称为圆柱体相交提取器）进行新颖的方式。我们的关键要素是这些设计的第一个驱动力，我们使用与编码理论和添加剂组合学的新连接获得了这些设计。
We study the problem of extracting random bits from weak sources that are sampled by algorithms with limited memory. This model of small-space sources was introduced by Kamp, Rao, Vadhan and Zuckerman (STOC'06), and falls into a line of research initiated by Trevisan and Vadhan (FOCS'00) on extracting randomness from weak sources that are sampled by computationally bounded algorithms. Our main results are the following. 1. We obtain near-optimal extractors for small-space sources in the polynomial error regime. For space $s$ sources over $n$ bits, our extractors require just $k\geq s\cdot$polylog$(n)$ entropy. This is an exponential improvement over the previous best result, which required $k\geq s^{1.1}\cdot2^{\log^{0.51} n}$ (Chattopadhyay and Li, STOC'16). 2. We obtain improved extractors for small-space sources in the negligible error regime. For space $s$ sources over $n$ bits, our extractors require entropy $k\geq n^{1/2+δ}\cdot s^{1/2-δ}$, whereas the previous best result required $k\geq n^{2/3+δ}\cdot s^{1/3-δ}$ (Chattopadhyay, Goodman, Goyal and Li, STOC'20). To obtain our first result, the key ingredient is a new reduction from small-space sources to affine sources, allowing us to simply apply a good affine extractor. To obtain our second result, we must develop some new machinery, since we do not have low-error affine extractors that work for low entropy. Our main tool is a significantly improved extractor for adversarial sources, which is built via a simple framework that makes novel use of a certain kind of leakage-resilient extractors (known as cylinder intersection extractors), by combining them with a general type of extremal designs. Our key ingredient is the first derandomization of these designs, which we obtain using new connections to coding theory and additive combinatorics.
