CCF: AF: Medium: Towards Optimal Pseudorandomness

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

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.