Analytic techniques in communication complexity, information complexity, and property testing

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

***Communication complexity is one of the most active fields of research in theoretical computer science. It has a broad range of applications, and employs a surprisingly diverse range of techniques and tools from other areas of mathematics (e.g. linear algebra, Fourier analysis, discrepancy theory, functional analysis, additive combinatorics, information theory, etc). In addition to its applications in other subfields of complexity theory, it has real world applications via data structures and data streaming algorithms. ***Although communication complexity has, since its birth, been witnessing steady and rapid progress, it was not until a few years ago that a focus on an information theoretic approach resulted in new and deeper understanding of some of the classical problems of the area. This gave birth to a new area of complexity theory called information complexity. While communication complexity is concerned with minimizing the amount of communication required for two players to evaluate a function that depends on their private inputs, information complexity, on the other hand, is concerned with the amount of information that the communicated bits reveal about the inputs of the two players. The field of information complexity is deeply connected to communication complexity. Shannon, in one of the most important mathematical papers of the 20th century, introduced the notion of entropy to capture the amount of information in a random variable, and set the foundations for the era of digital communication. Shannon's setting is the simplest setting of communication where there is a one-way channel and one player wants to transmit her data to the other player. The general setting of communication complexity is more complicated as the players are allowed to interact. However as the recent results in this area have demonstrated, similar to the way that the information content of a random variable gives the asymptotics of the transmission cost, information complexity of a function provides valuable information about the communication complexity.*** ***One of the main goals of this proposal is to study protocols with optimal information cost and in particular to find a paradigm in which such protocols can be defined properly. This is important as currently we have little understanding of how the optimal protocols look like. The second goal of this proposal is to extend the information theoretic approach to other areas of complexity theory, and the third goal of this proposal is to investigate further applications of recent advances in additive combinatorics to communication complexity and the area of property testing. Additive combinatorics has seen exciting advances in recent years. Some of the tools in this field has found applications in theoretical computer science. We propose to study further applications of these techniques in the areas of communication complexity and property testing.*****