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

点击翻译按钮获取中文摘要

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.