CCF: AF: Medium: Towards Optimal Pseudorandomness

对于许多问题，随机算法比不使用随机性的已知算法提供了显著的加速。然而，随机化在算法的结果中引入了不确定性，因为会有很小的错误概率。这个项目的目的是探索在保持速度的同时，什么时候可以消除不确定性。该项目整合了教育和推广，包括指导学生、公开讲座和科普写作。研究人员将重点关注伪随机性研究中的两个基本基元：随机提取器和伪随机发生器。随机提取器将低质量的随机转化为高质量的随机。伪随机生成器将短随机字符串转换为长“伪随机”字符串，这对于许多用途来说已经足够好了。这些原语有许多远远超出其原始目的的应用，包括密码学、编码理论、近似硬度和数据结构。该领域以前的工作主要集中在多项式时间上，没有更精确地分析减速。在这个项目中，研究人员的目标是改进随机提取器和伪随机生成器的关键参数，从而在从算法中去除随机性时实现最小的减速。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.