AF: Small: Foundational Research in Communication Complexity and Its Applications

通信复杂性是对计算问题的研究，其中输入被分散到多个位置，描述为参与通信游戏的各方。这些各方必须根据协议相互通信，以解决利益问题，同时最小化通信量（交换的比特数）。除了其内在动机（由即将到来的“云计算”时代增强），通信复杂性的重要性源于其在理论计算机科学的所有其他领域的含义，甚至是那些不直接涉及通信的领域；例如电路复杂性、数据流、查询复杂性、属性测试和博弈论。在这个奖项下，PI和他的学生将研究一些具体的交流游戏，不仅试图在特定问题上建立新的界限，而且通过新的技术和范式拓宽该领域的基础。由此发现的结果和思想将应用于上面提到的一些领域，特别关注数据流算法。有代表性的研究目标如下：(1)发展梅林-亚瑟通信理论，着眼于与强大但不受信任的助手交互的数据流算法的应用。(2)通过新的通信下界或改进的算法，加深我们对一些图流问题的理解。(3)将最新的信息复杂性分析技术与已有的通信复杂性分析技术联系起来。该奖项的更广泛影响包括培训最多两名研究生，他们可以从事通信复杂性或其应用的任何方面的工作，以及设计和教授一门新的关于通信协议和复杂性的研究生课程。取得的成果将在国际会议、其他机构的专题讲习班和研讨会上传播。

Communication complexity is the study of computational problems where the input is split amongst multiple locations, described as parties playing a communication game. These parties must communicate with one another according to a protocol to solve the problem of interest, while minimizing the amount of communication (number of bits exchanged). Besides its intrinsic motivation (enhanced by the coming "cloud computing" era), communication complexity derives its importance from its implications in all sorts of other areas of theoretical computer science, even ones that do not directly involve communication; examples are circuit complexity, data streaming, query complexity, property testing, and game theory.Under this award, the PI and his students will investigate a number of concrete communication games, attempting not just to establish new bounds on specific problems, but also to broaden the foundations of the field through new techniques and paradigms. Results and ideas thus discovered will be applied to some of the areas mentioned above, with a particular focus on data stream algorithms. Some representative research goals are as follows. (1) Developing the theory of Merlin-Arthur communication, with a view towards applications to data stream algorithms that interact with a powerful but untrusted helper. (2) Deepening our understanding of a number of graph streaming problems, either through new communication lower bounds or improved algorithms. (3) Relating the recent technique of information complexity to older established techniques for analyzing communication complexity.The broader imapcts of the award include the training of up to two graduate students who may work on any aspect of communication complexity or its applications, and the design and teaching of a new graduate-level course on communication protocols and complexity. Results obtained will be disseminated at international conferences, targeted workshops and seminars at other institutions.