AF: EAGER: Identifying Opportunities in Pseudorandomness

伪随机性是一种生成“看起来随机”的对象的理论，尽管这些对象是使用很少或没有随机性来构造的。 伪随机性的计算理论起源于20世纪80年代初的密码学基础，此后发展成为理论计算机科学的一个丰富的子领域。 伪随机理论中研究的概念和结构对计算机科学、通信和数学等许多不同的研究领域都有影响。EARLY概念探索性研究资助（EAGER）项目旨在确定新的方法来应对伪随机中一些最持久和最重要的挑战，以及伪随机新应用的机会。 这项研究将与PI的教育工作紧密结合。 特别是，PI将继续开发新的课程，教育和教学材料，供其他人公开使用。 研究生和本科生将参与这项研究的各个阶段，并将有机会在顶级国际会议上发表和展示他们的成果。 研究员也将继续为科学界提供广泛的服务。具体来说，该项目将试图发现新的方法来解决以下问题：1。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?