AF: Small: Randomness Extraction and Pseudorandomness

AF：小：随机性提取和伪随机性

• 批准号: 2008076
• 负责人: David Zuckerman
• 金额: $ 40万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-10-01 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2008076&HistoricalAwards=false
• 关键词: AF; Small; Randomness; Extraction; Pseudorandomness

Random numbers are surprisingly useful in computer science. For example, they are used for simulations of complex systems, such as the weather and the economy. In addition, randomness is essential for "streaming algorithms," where there is so much data arriving that it is impossible to store it all. Moreover, randomness is vital for computer security. While randomness has many applications, truly random numbers are difficult to obtain. It is therefore important to develop techniques to get by with less randomness or lower quality randomness. The main tool to reduce the amount of randomness required is a pseudorandom number generator. In contrast, the main tool to reduce the quality of randomness required is a randomness extractor.This proposal addresses important questions about pseudorandom generators and randomness extractors that relate to the investigator's recent work. For example, the investigator and his student gave an efficient algorithm that extracts randomness from two independent sources of low-quality randomness that was dramatically better than previously known. However, the error is too large for applications in cryptography. The investigator proposes to improve this, as well as work on other aspects of randomness extraction. The investigator also proposes to construct pseudorandom generators that work for large classes of randomized algorithms, such as those using a small amount of memory. Finally, the investigator proposes work connecting these objects to seemingly unrelated areas, such as big data in the form of streaming algorithms.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

随机数在计算机科学中非常有用。例如，它们用于模拟复杂系统，例如天气和经济。 此外，随机性对于“流算法”至关重要，因为到达的数据如此之多，以至于不可能将其全部存储。 此外，随机性对于计算机安全至关重要。 虽然随机性有很多应用，但真正的随机数很难获得。 因此，开发能够减少随机性或降低质量随机性的技术非常重要。 减少所需随机性的主要工具是伪随机数生成器。相反，降低所需随机性质量的主要工具是随机性提取器。该提案解决了与研究者近期工作相关的伪随机生成器和随机性提取器的重要问题。 例如，研究人员和他的学生给出了一种有效的算法，可以从两个独立的低质量随机性来源中提取随机性，该算法比以前已知的要好得多。然而，对于密码学中的应用来说，误差太大。研究人员建议改进这一点，并致力于随机性提取的其他方面。 研究人员还建议构建适用于大类随机算法的伪随机生成器，例如使用少量内存的算法。 最后，研究人员提出将这些对象与看似不相关的领域连接起来的工作，例如流算法形式的大数据。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力优点和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Almost Chor-Goldreich Sources and Adversarial Random Walks

几乎 Chor-Goldreich 来源和对抗性随机游走

• DOI: 10.1145/3564246.3585134
• 发表时间: 2023-06
• 期刊: Proceedings of the annual ACM Symposium on Theory of Computing
• 作者: Doron, Dean;Moshkovitz, Dana;Oh, Justin;Zuckerman, David
• 通讯作者: Zuckerman, David

Extractors for Images of Varieties

品种图像提取器

• DOI: 10.1145/3564246.3585109
• 发表时间: 2023-06
• 期刊: Conference proceedings of the annual ACM Symposium on Theory of Computing
• 作者: Guo, Zeyu;Volk, Ben Lee;Jalan, Akhil;Zuckerman, David
• 通讯作者: Zuckerman, David