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.