CRII: AF: Developing and Applying Connections Between Communication Complexity and Query Complexity

计算复杂性的目的是证明解释资源约束下计算的基本限制的定理。随着云计算和大数据的趋势，(不同各方之间的)通信和(对输入的)查询这两种资源变得越来越重要。PI和其他人最近的研究揭示了复杂性理论的这两个子领域之间的深刻联系，即通信复杂性和查询复杂性，并应用这些联系解决了理论计算机科学和其他领域中几个基本和长期悬而未决的问题。这个项目将进一步发展这些联系并探索新的应用，这将有助于确定哪些问题可以通过计算机科学其他领域的有效计算过程解决，哪些不可以。这个项目的更广泛的影响包括培训和支持研究生的研究生涯，通过在线参考资源和说明性文章广泛传播研究成果，机构层面的课程开发，研究和教学的结合，少数群体参与研究，与数学家合作，以及推广努力。沟通复杂性和查询复杂性之间的联系被形式化地描述为“模拟定理”，表明在某些情况下，决策树可以模拟相关问题的通信协议。PI将开发证明新的模拟定理所需的数学技术，并对现有的模拟定理进行量化改进。这些结果将有助于建立通信下限的“统一理论”，显示出一种分离的关注点，其中简单的特定于问题的查询复杂性下限可以与处理通信协议的通用(但深入的)机制相结合。该项目还将探索这种联系的新应用，例如获得通信复杂性度量的新下界和分离，发展线性规划的“细粒度扩展复杂性”理论，回答关于通信和关于如何有效地估计给定函数的复杂性的结构性问题，以及研究关于查询复杂性度量行为的基本开放问题。

The aim of computational complexity is to prove theorems that explain the fundamental limits of computation under resource constraints. Two such resources, communication (between different parties) and queries (to the input), have become increasingly important with the trends toward cloud computing and big data. Recent research by the PI and others has uncovered deep connections between these two subfields of complexity theory, namely communication complexity and query complexity, and has applied these connections to resolve several fundamental and long-standing open problems in theoretical computer science and beyond. This project will further develop these connections and explore new applications, which will help identify which problems can and cannot be solved by efficient computational processes in other areas of computer science. The broader impacts of this project include training and supporting the research careers of graduate students, broad dissemination of research findings through online reference resources and expository articles, curriculum development at the institutional level for the integration of research and teaching, involvement of minorities in research, collaboration with mathematicians, and outreach efforts.The connections between communication complexity and query complexity are formalized as "simulation theorems" showing that in certain situations, decision trees can simulate communication protocols for related problems. The PI will develop the mathematical techniques needed to prove new simulation theorems and obtain quantitative improvements to existing ones. These results will contribute to a "unified theory" of communication lower bounds, showing a separation of concerns in which simple problem-specific query complexity lower bounds can be combined with generic (but deep) machinery for handling communication protocols. The project will also explore new applications of such connections, such as obtaining new lower bounds and separations for communication complexity measures, developing a theory of "fine-grained extension complexity" for linear programming, answering structural questions about communication and about how efficiently the complexity of a given function can be estimated, as well as studying fundamental open questions about the behavior of query complexity measures.