AF: Small: Challenges in Communication Complexity and Pseudorandomness

该项目解决了两个密切相关领域的核心问题：通信复杂性和伪随机性。当输入在不同方之间分配时，完成计算任务所需的最小通信量是多少？这些问题在理论和实践上都有着深远的应用，特别是在通信日益成为大规模计算的瓶颈的情况下。该项目的一个目标是证明元定理，并开发通用技术，将理解沟通简化为更简单的“决策理论”问题。宇宙中的随机性与决定论是一场古老的哲学辩论。然而，在计算领域，随机性似乎正在凭借在密码学、电子商务、数据分析、算法设计和网络方面的惊人应用轻松取胜。这些应用中有哪些绝对需要随机性？如果我们没有随机比特或只能访问有缺陷的随机比特(如来自无线电活动衰变的数据)，那么它们中的哪些仍然可以模拟？该项目将研究将内存作为资源进行优化时的这些基本问题：我们是否可以在内存中只有很小的开销来确定性地模拟随机算法？研究人员将开发并免费提供关于这些前沿研究问题的教育材料，并指导本科生和研究生进行这些主题的研究。更详细地说，该项目旨在开发一种全面的通信中的“提升定理”理论，它将证明通信下界简化为证明通常更简单的查询复杂性下界。该项目将专注于这一领域的两个中心开放问题：固定大小小工具的提升和半定优化的提升。研究人员还将探索多方通信复杂性与密码学和抽取器中的泄密弹性之间的新应用和联系。该项目还寻求为小宽度分支计划设计最佳伪随机发生器，这将是理解随机性和空间之间权衡的重要一步。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The project addresses central questions within two closely related areas: communication complexity, and pseudorandomness. What is the minimal amount of communication needed to complete a computational task when the input is split between different parties? Such questions have profound applications both in theory and in practice, especially as communication is increasingly becoming the bottleneck in large-scale computation. A goal of the project is to prove meta-theorems and develop generic techniques that reduce understanding communication to much simpler 'decision-theoretic' problems. Randomness versus determinism in the universe is an ancient philosophical debate. In computing, however, randomness seems to be winning hands down with amazing applications in cryptography, e-commerce, data analytics, algorithm design, and networking. Which of these applications absolutely need randomness? Which of them can still be simulated if we do not have random bits or have access only to defective random bits as in data from radio-active decay? The project will study these fundamental questions when optimizing for memory as a resource: Can we simulate randomized algorithms deterministically with only a small overhead in memory? The investigator will develop and make freely available educational material on these cutting-edge research problems and guide undergraduate and graduate students on performing research on these topics. In more detail, the project aims to develop a comprehensive theory of 'lifting theorems' in communication, which reduce proving communication lower bounds to proving query-complexity lower bounds that are often simpler. The project will focus on the two central open problems in this area: lifting for constant-size gadgets, and lifting for semi-definite optimization. The investigator will also explore new applications and connections between multi-party communication complexity and leakage-resilience in cryptography and extractors. The project also seeks to design optimal pseudorandom generators for small-width branching programs, which would be a significant step toward understanding the trade-off between randomness and space.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.