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

AF：小型：通信复杂性及其应用的基础研究

• 批准号: 1217375
• 负责人: Amit Chakrabarti
• 金额: $ 44万
• 依托单位: Dartmouth College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1217375&HistoricalAwards=false
• 关键词: AF; Small; Foundational; Research; Communication

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.

沟通复杂性是对计算问题的研究，在这些计算问题中，其中的输入在多个位置之间进行了分配，被描述为在玩通信游戏的各方。 这些当事方必须根据协议相互交流，以解决感兴趣的问题，同时最大程度地减少交流数量（交换的位数）。 除了它的内在动机（通过即将到来的“云计算”时代增强）之外，沟通复杂性从对理论计算机科学的其他各种领域的含义也从其含义中得出了重要性，即使是那些不直接涉及沟通的领域。示例是电路复杂性，数据流，查询复杂性，财产测试和游戏理论。在此奖项下，PI和他的学生将研究许多具体的通信游戏，不仅试图建立有关特定问题的新界限，还试图通过新技术和范式扩大领域的基础。因此发现的结果和想法将应用于上述某些领域，特别关注数据流算法。 一些代表性的研究目标如下。 （1）发展Merlin-Arthur通信的理论，以期待与功能强大但不信任的助手相互作用的数据流算法。 （2）通过新的通信下限或改进的算法加深我们对许多图流问题的理解。 （3）将最近的信息复杂性技术与较旧的已建立的技术相关联，以分析沟通复杂性。该奖项的更广泛的IMAPCT包括培训多达两名研究生，这些研究生可以在交流复杂性或其应用程序的任何方面工作，以及有关沟通协议和复杂性的新研究生级课程的设计和教学。 获得的结果将在其他机构的国际会议，有针对性的研讨会和研讨会上传播。