CCF: AF: Medium: Towards Optimal Pseudorandomness

CCF：AF：中：走向最佳伪随机性

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

For many problems, randomized algorithms offer significant speedups over known algorithms that don’t use randomness. However, randomization introduces uncertainty in the outcome of the algorithm, as there will be a small probability of error. The purpose of this project is to explore when uncertainty can be eliminated while maintaining speed. The project integrates education and outreach, including mentoring of students, public lectures and popular science writing.The investigators will focus on two fundamental primitives in the study of pseudorandomness: randomness extractors and pseudorandom generators. A randomness extractor transforms low-quality randomness into high-quality randomness. A pseudorandom generator converts a short random string into a long ``pseudorandom" string that is good enough for many purposes. These primitives have had many applications far beyond their original purpose, including to cryptography, coding theory, hardness of approximation, and data structures. Previous work in this area mostly focused on polynomial time, without analyzing the slowdowns more precisely. In this project, the investigators aim to improve key parameters of randomness extractors and pseudorandom generators that will enable minimal slowdowns when removing the randomness from 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的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。