AF: Medium: Collaborative Research: Exploiting Opportunities in Pseudorandomness

点击翻译按钮获取中文摘要

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.