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+\delta}\cdot s^{1/2-\delta}$, whereas the previous best result required $k\geq n^{2/3+\delta}\cdot s^{1/3-\delta}$ (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.
翻译:我们研究从微弱来源提取随机比特的问题,这些微弱来源由内存有限的算法取样。这种小空间来源模型是由Kamp、Rao、Vadhan和Zuckerman(STOC'06)推出的,并落入Trevisan和Vadhan(FoCS'00)在从微弱来源提取随机性,这些微弱来源通过计算捆绑的算法取样。我们的主要结果如下。1. 我们在多边错误制度中为小型空间来源获取接近最佳的提取器。对于以美元为单位的空间源而言,我们的微小空间源需要用美元为单位,我们的微小空间源需要以美元为单位,而我们的资源需要以美元为单位,现在需要以美元为单位,现在需要以美元为单位。