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.