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.

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

项目成果

Extractors for Images of Varieties

• DOI: 10.1145/3564246.3585109
• 发表时间: 2022-11
• 期刊: Proceedings of the 55th Annual ACM Symposium on Theory of Computing
• 作者: Zeyu Guo;Ben lee Volk;Akhil Jalan;David Zuckerman

Almost Chor-Goldreich Sources and Adversarial Random Walks

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