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)将最新的信息复杂性技术与旧的通信复杂性分析技术联系起来。该奖项的更广泛影响包括培训最多两名研究生，他们可能从事通信复杂性或其应用的任何方面的工作，以及设计和教学一门新的关于通信协议和复杂性的研究生课程。所取得的成果将在其他机构的国际会议、有针对性的讲习班和研讨会上传播。