AF: Small: Intermediate models between communication complexity and query complexity

AF：小：通信复杂度和查询复杂度之间的中间模型

基本信息

批准号：
2006443
负责人：
Shachar Lovett
金额：
$ 30万
依托单位：
University of California-San Diego
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-08-01 至 2024-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2006443&HistoricalAwards=false
关键词：
AF Small Intermediate models between

项目摘要

Communication complexity has been a vibrant sub-field of computer science for more than 40 years. At its core, it studies distributed problems, where each player receives a part of a problem, and the players need to cooperate and share information in order to find a solution. Many of the celebrated results in the field involve figuring out exactly how much communication is needed to solve certain concrete important problems with relevance in many other domains in computer science. On the other hand, there are only few techniques to understand general communication problems.This is in contrast with the situation in simpler computational models, notably query complexity. It is safe to say that today there is a complete qualitative, and to a large extent quantitative, understanding of the query complexity of generic problems. The focus of this project is on intermediate models, which interpolate between communication complexity and query complexity. The goal is to to understand fundamental open problems in communication complexity in these restricted models, in order to develop new tools and techniques that then may be extended to general communication complexity.The main questions in communication complexity that this award aims to tackle are:* Which functions admit efficient communication protocols?* Are there algebraic, analytic or combinatorial properties that characterize such functions?* What is the structure of efficient communication protocols?* What is the power of randomness in communication complexity?The plan is to consider these questions restricted to a special class of problems, called lifted functions. These contain many natural examples of well-studied functions, and also give rise to natural intermediate models, such as parity decision trees and AND decision trees. These models are more powerful than standard query complexity, and more structured than general communication complexity, and as such are an ideal test bed to develop new techniques.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.

40 多年来，通信复杂性一直是计算机科学的一个充满活力的子领域。它的核心是研究分布式问题，其中每个玩家都会收到问题的一部分，并且玩家需要合作并共享信息才能找到解决方案。该领域的许多著名成果都涉及准确地计算出需要多少通信才能解决与计算机科学许多其他领域相关的某些具体重要问题。另一方面，理解一般通信问题的技术很少。这与更简单的计算模型的情况形成鲜明对比，尤其是查询复杂性。可以肯定地说，今天对通用问题的查询复杂性有了完整的定性理解，并且在很大程度上是定量的。该项目的重点是中间模型，它在通信复杂性和查询复杂性之间进行插值。目标是了解这些受限模型中通信复杂性的基本开放问题，以便开发新的工具和技术，然后可以扩展到一般通信复杂性。该奖项旨在解决的通信复杂性的主要问题是：*哪些函数允许有效的通信协议？* 是否存在表征这些函数的代数、解析或组合属性？* 有效通信协议的结构是什么？* 通信复杂性中随机性的力量有多大？计划是考虑限制这些问题对于一类特殊的问题，称为提升函数。其中包含许多经过深入研究的函数的自然示例，并且还产生了自然中间模型，例如奇偶决策树和 AND 决策树。这些模型比标准查询复杂性更强大，比一般通信复杂性更结构化，因此是开发新技术的理想测试平台。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力评估进行评估，被认为值得支持。优点和更广泛的影响审查标准。