权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

AF: Small: Challenges in Communication Complexity and Pseudorandomness

AF：小：通信复杂性和伪随机性的挑战

基本信息

批准号：
2007682
负责人：
Raghu Meka
金额：
$ 40万
依托单位：
University of California-Los Angeles
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-07-01 至 2024-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2007682&HistoricalAwards=false
关键词：
AF Small Challenges Communication Complexity

项目摘要

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.

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