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

40多年来，通信复杂性一直是计算机科学中一个充满活力的子领域。它的核心是研究分布式问题，每个参与者都会收到问题的一部分，参与者需要合作和共享信息才能找到解决方案。该领域的许多著名成果涉及准确地计算出需要多少沟通才能解决与计算机科学的许多其他领域相关的某些具体、重要的问题。另一方面，只有很少的技术可以理解一般的通信问题。这与更简单的计算模型中的情况形成了鲜明对比，特别是查询复杂性。可以肯定地说，今天对一般问题的查询复杂性有了完全的定性和很大程度上的定量理解。该项目的重点是介于通信复杂性和查询复杂性之间的中间模型。目的是了解这些受限模型中通信复杂性的基本公开问题，以便开发新的工具和技术，然后可以扩展到一般的通信复杂性。本奖项旨在解决的通信复杂性的主要问题是：*哪些函数允许有效的通信协议？*这些函数是否具有代数、解析或组合性质？*高效通信协议的结构是什么？*通信复杂性中的随机性的力量是什么？计划是将这些问题限制在一类特殊的问题上，称为提升函数。这些包含了许多经过充分研究的函数的自然示例，并且还产生了自然的中间模型，例如奇偶决策树和和决策树。这些模型比标准查询复杂性更强大，比一般通信复杂性更具结构化，因此是开发新技术的理想试验台。该奖项反映了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.