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. 我们在多边错误制度中为小型空间来源获取接近最佳的提取器。对于以美元为单位的空间源而言,我们的微小空间源需要用美元为单位,我们的微小空间源需要以美元为单位,而我们的资源需要以美元为单位,现在需要以美元为单位,现在需要以美元为单位。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
123+阅读 · 2020年9月8日
【NeurIPS 2019的主要趋势】Key trends from NeurIPS 2019
专知会员服务
11+阅读 · 2019年12月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
计算机视觉最佳实践、代码示例和相关文档
专知会员服务
17+阅读 · 2019年10月9日
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
已删除
将门创投
3+阅读 · 2019年9月4日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
trape 一种识别工具
黑白之道
4+阅读 · 2019年5月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年9月22日
VIP会员
相关VIP内容
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
123+阅读 · 2020年9月8日
【NeurIPS 2019的主要趋势】Key trends from NeurIPS 2019
专知会员服务
11+阅读 · 2019年12月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
计算机视觉最佳实践、代码示例和相关文档
专知会员服务
17+阅读 · 2019年10月9日
相关资讯
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
已删除
将门创投
3+阅读 · 2019年9月4日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
trape 一种识别工具
黑白之道
4+阅读 · 2019年5月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员