AF: Medium: Collaborative Research: Exploiting Opportunities in Pseudorandomness

该项目寻求利用新的机会来推进伪随机性理论，即生成“看起来随机”的对象的理论，尽管它的构造使用很少或没有随机性。伪随机计算理论起源于20世纪80年代初密码学的基础，并已发展成为理论计算机科学的一个丰富的子领域。伪随机理论中研究的概念和结构对计算机科学、通信和数学的许多不同领域的研究都有影响，包括密码学、计算复杂性、编码理论、加性数论、度量嵌入、流和素描算法以及图论。该项目高度重视教育、服务研究界和广泛传播知识。研究活动将与课程开发、研究咨询、服务和推广相结合。此外，该研究还涉及国家对社会重要的优先事项，如安全和隐私。具体来说，该项目寻求在几个基本问题上取得进展的新机会，包括：1)RL vs. L问题：试图无条件地证明，每个随机算法都可以是确定性的，只有空间效率的恒定因素损失；2)显式构造：寻求显式的负载均衡哈希函数、批处理代码和深度鲁棒图，实现实质性的参数改进，对应用具有定性意义。3)应用：改进和扩展伪随机性在密码学和数据结构中的应用。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This project seeks to exploit new opportunities to advance the theory of pseudo-randomness, which is the theory of generating objects that "look random" despite being constructed using little or no randomness. The computational theory of pseudo-randomness originated in the foundations of cryptography in the early 1980s and has since developed into a rich sub-field of theoretical computer science in its own right. The notions and constructs studied in the theory of pseudo-randomness have implications for many different areas of research in computer science, communications, and mathematics, including cryptography, computational complexity, coding theory, additive number theory, metric embeddings, streaming and sketching algorithms, and graph theory. The project puts high value on education, service to the research community, and wide dissemination of knowledge. The research activities will be accompanied by and integrated with curriculum development, research advising, service, and outreach. In addition, the research also relates to national priorities of importance to society, such as security and privacy.Specifically, the project seeks to exploit new opportunities for progress on several fundamental questions, including: 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 space efficiency; 2) Explicit constructions: seeking explicit load-balancing hash functions, batch codes, and depth-robust graphs that achieve substantial parameter improvements and have qualitative significance for applications, and 3) Applications: improving and extending the applications of pseudo-randomness to cryptography and data structures.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.