Pseudorandomness is the theory of generating objects that "look random" despite being constructed using little or no randomness. The computational theory of pseudorandomness originated in the foundations of cryptography in the early 1980s and has since developed into a rich subfield of theoretical computer science in its own right. The notions and constructs studied in the theory of pseudorandomness have implications for many different areas of research in computer science, communications, and mathematics.
This EArly-concept Grant for Exploratory Research (EAGER) project seeks to identify novel approaches to some of the most enduring and important challenges in pseudorandomness as well as opportunities for new applications of pseudorandomness. The research will be closely integrated with the PIs' educational efforts. In particular, the PIs will continue to develop new curricular, educational, and expository material that are made openly available for others to use. Graduate and undergraduate students will be involved in all phases of this research, and will be given opportunities to publish and present their results at premier international conferences. The PIs will also continue their extensive service to the scientific community.
Specifically, the project will try to uncover new approaches to topics such as:
1. The RL vs. L problem: trying to prove, unconditionally, that every randomized algorithm can be made deterministic with only a constant-factor loss in memory usage.
2. Cryptography: identifying optimally efficient constructions of cryptographic primitives from minimal assumptions.
3. Machine Learning: can pseudorandomness help in making machine learning robust to adversarial noise or to overfitting?
