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

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

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.