AF: EAGER: Identifying Opportunities in Pseudorandomness

伪随机性是指生成看似随机的对象的理论，尽管它的构造很少或根本没有随机性。伪随机计算理论起源于20世纪80年代初密码学的基础，并已发展成为理论计算机科学的一个丰富的分支领域。伪随机理论中研究的概念和结构对计算机科学、通信和数学等许多不同领域的研究都有影响。这个早期概念探索性研究（EAGER）项目旨在确定解决伪随机性中一些最持久和最重要挑战的新方法，以及伪随机性新应用的机会。这项研究将与pi的教育工作密切结合。特别是，pi将继续开发新的课程、教育和说明性材料，这些材料将公开供其他人使用。研究生和本科生将参与这项研究的所有阶段，并将有机会在主要的国际会议上发表和展示他们的成果。pi还将继续为科学界提供广泛的服务。具体来说，该项目将尝试发现以下主题的新方法：RL vs. L问题：试图无条件地证明每个随机算法都可以在内存使用中只有恒定因素损失的情况下具有确定性。密码学：从最小假设中识别出最有效的密码学原语结构。机器学习：伪随机性是否有助于使机器学习对对抗噪声或过拟合具有鲁棒性？

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?