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

CRII：AF：开发和应用通信复杂性和查询复杂性之间的联系

• 批准号: 1657377
• 负责人: Thomas Watson
• 金额: $ 17.49万
• 依托单位: University of Memphis
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-07-01 至 2020-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1657377&HistoricalAwards=false
• 关键词: CRII; AF; Developing; Applying; Connections

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.

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

项目成果

EXTENSION COMPLEXITY OF INDEPENDENT SET POLYTOPES

• DOI: 10.1137/16m109884x
• 发表时间: 2018-01-01
• 期刊: SIAM JOURNAL ON COMPUTING
• 影响因子: 1.6
• 作者: Goeoes, Mika;Jain, Rahul;Watson, Thomas
• 通讯作者: Watson, Thomas

Query-to-Communication Lifting for P^NP

P^NP 的查询到通信提升

• DOI: 10.4230/lipics.ccc.2017.12
• 发表时间: 2017
• 期刊: Proceedings of the 32nd Computational Complexity Conference (CCC
• 作者: Göös, Mika;Kamath, Pritish;Pitassi, Toniann;Watson, Thomas
• 通讯作者: Watson, Thomas

The Landscape of Communication Complexity Classes

通信复杂性类的概况

• DOI: 10.1007/s00037-018-0166-6
• 发表时间: 2018
• 期刊: computational complexity
• 影响因子: 1.4
• 作者: Göös, Mika;Pitassi, Toniann;Watson, Thomas
• 通讯作者: Watson, Thomas

Quadratic Simulations of Merlin-Arthur Games

Merlin-Arthur 游戏的二次模拟

• DOI: 10.1007/978-3-319-77404-6_62
• 发表时间: 2018
• 期刊: Proceedings of the 13th Latin American Theoretical Informatics Symposium (LATIN
• 作者: Watson, Thomas

A ZPP^NP[1] Lifting Theorem

ZPP^NP[1] 提升定理

• DOI: 10.4230/lipics.stacs.2019.59
• 发表时间: 2019
• 期刊: Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS
• 作者: Watson, Thomas