CAREER: Structural Communication Complexity

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

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.