CAREER: Structural Communication Complexity

职业：结构通信复杂性

• 批准号: 1942742
• 负责人: Thomas Watson
• 金额: $ 42.74万
• 依托单位: University of Memphis
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-10-01 至 2025-09-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1942742&HistoricalAwards=false
• 关键词: CAREER; Structural; Communication; Complexity

The field of communication complexity is about situations where twoparties, call them Alice and Bob, each hold a separate piece of data,and they wish to collaboratively solve some computational problem thatdepends on both their inputs. How much will they need to communicateback-and-forth to achieve their goal? The field encompasses both upperbounds---i.e., the design of protocols that allow Alice and Bob tosucceed using only a small amount of communication---as well as lowerbounds---which show that no such efficient protocol exists for certainproblems (i.e., Alice and Bob will need to communicate many bits tosucceed). This serves as a natural model of distributed computing,motivated by big data and cloud computing concerns. More generally, itcan be used to model any situation where flow of information betweendifferent components of a system forms a bottleneck; for this reason,communication complexity has applications to many other areas ofcomputer science. This project will develop deep technical tools to makeprogress on several longstanding problems and central issues incommunication complexity and its various application areas. The unifyingtheme of this project is the importation of insights and techniques fromstructural complexity, which is the area of theoretical computer sciencedevoted to classifying problems according to their inherentcomputational difficulty. The education component will address thechallenges of facilitating flow of ideas between theory andapplications, and transitioning students from coding to problem solvingto research.One specific type of tool relevant to this project is "liftingtheorems", which relate communication complexity to the simpler model ofquery complexity. The investigator will continue to develop and applysuch lifting theorems to address structural questions in communicationcomplexity and beyond. This project will: develop fundamentally newlower bound techniques for powerful communication models, strengthen andunify classic and widely-used results, clarify the delicate relationshipbetween communication and the amount of information Alice and Bob revealabout their inputs, advance the understanding of computational problemsconcerning communication complexity itself, and use structural insightsto deepen the connections with circuit complexity, proof complexity, anddata structures.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.

通信复杂性的领域是关于这样的情况：两个人，称为Alice和Bob，每个人持有单独的一段数据，他们希望协作解决一些依赖于他们两个输入的计算问题。他们需要多少来回交流才能实现他们的目标？该字段包括两个上界-即，允许Alice和Bob仅使用少量通信成功的协议的设计-以及下限-这表明对于某些问题不存在这样的有效协议(即，Alice和Bob将需要通信许多比特才能成功)。这是一种自然的分布式计算模型，受大数据和云计算的推动。更广泛地说，它可以用来模拟系统不同组件之间的信息流形成瓶颈的任何情况；因此，通信复杂性应用于计算机科学的许多其他领域。该项目将开发深入的技术工具，以在通信复杂性及其各种应用领域中的几个长期存在的问题和核心问题上取得进展。这个项目的统一主题是从结构复杂性中引入见解和技术，结构复杂性是理论计算机科学的领域，致力于根据问题本身的计算难度对问题进行分类。教育部分将解决促进理论和应用之间的思想流动，以及将学生从编码过渡到问题解决到研究的挑战。与此项目相关的一种特定类型的工具是“提升定理”，它将通信复杂性与更简单的查询复杂性模型联系起来。研究人员将继续开发和应用这样的提升定理，以解决通信复杂性和其他方面的结构性问题。这个项目将：为强大的通信模型开发全新的下限技术，加强和统一经典和广泛使用的结果，澄清通信与Alice和Bob透露的关于其输入的信息量之间的微妙关系，促进对关于通信复杂性本身的计算问题的理解，并使用结构洞察力加深与电路复杂性、证明复杂性和数据结构的联系。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Query-to-Communication Lifting for BPP

BPP 的查询到通信提升

• DOI: 10.1137/17m115339x
• 发表时间: 2020
• 期刊: SIAM Journal on Computing
• 影响因子: 1.6
• 作者: Göös, Mika;Pitassi, Toniann;Watson, Thomas
• 通讯作者: Watson, Thomas

Complexity of Fault Tolerant Query Complexity

容错查询复杂度

• 发表时间: 2022
• 期刊: Track A
• 作者: Maharjan, Ramita;Watson, Thomas
• 通讯作者: Watson, Thomas

6-Uniform Maker-Breaker Game Is PSPACE-Complete

6-Uniform Maker-Breaker 游戏已 PSPACE 完成

• DOI: 10.4230/lipics.stacs.2021.57
• 发表时间: 2021
• 期刊: Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS
• 作者: Rahman, Md Lutfar;Watson, Thomas
• 通讯作者: Watson, Thomas

A Lower Bound for Sampling Disjoint Sets

不相交集采样的下界

• DOI: 10.4230/lipics.approx-random.2019.51
• 发表时间: 2019
• 期刊: Proceedings of the 23rd International Conference on Randomization and Computation (RANDOM
• 作者: Göös, Mika;Watson, Thomas
• 通讯作者: Watson, Thomas

When Is Amplification Necessary for Composition in Randomized Query Complexity?

随机查询复杂度中的组合何时需要放大？

• DOI: 10.4230/lipics.approx/random.2020.28
• 发表时间: 2020
• 期刊: Proceedings of the 24th International Conference on Randomization and Computation (RANDOM
• 作者: Ben-David, Shalev;Göös, Mika;Kothari, Robin;Watson, Thomas
• 通讯作者: Watson, Thomas