AF: EAGER: Identifying Opportunities in Pseudorandomness

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