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

通信复杂性是理论计算机科学中最活跃的研究领域之一。它具有广泛的应用范围，并使用了来自其他数学领域(例如，线性代数、傅立叶分析、偏差理论、泛函分析、加法组合学、信息论等)的各种技术和工具，令人惊讶地多样化。除了在复杂性理论的其他子领域中的应用外，它还通过数据结构和数据流算法在现实世界中得到应用。*尽管通信复杂性自诞生以来一直在稳步和快速地发展，但直到几年前，对信息论方法的关注才导致对该领域一些经典问题的新的和更深入的理解。这催生了复杂性理论的一个新领域，称为信息复杂性。虽然通信复杂性涉及最小化两个参与者评估依赖于他们的私人输入的函数所需的通信量，但另一方面，信息复杂性涉及通信比特揭示的关于两个参与者的输入的信息量。信息复杂性领域与通信复杂性息息相关。香农在20世纪最重要的数学论文之一中，引入了熵的概念，以捕捉随机变量中的信息量，并为数字通信时代奠定了基础。香农的设置是最简单的通信设置，其中有一个单向通道，一个玩家想要将她的数据传输给另一个玩家。随着玩家被允许交互，通信复杂性的一般设置更加复杂。然而，这一领域的最新结果表明，类似于随机变量的信息量给出了传输成本的渐近性，函数的信息复杂性提供了关于通信复杂性的有价值的信息。*该建议的主要目标之一是研究具有最优信息成本的协议，特别是找到一种可以适当地定义此类协议的范例。这一点很重要，因为目前我们对最佳协议是什么样子知之甚少。该建议的第二个目标是将信息论方法扩展到复杂性理论的其他领域，该建议的第三个目标是研究加性组合学的最新进展在通信复杂性和性质测试领域的进一步应用。近年来，加性组合数学取得了令人振奋的进展。这一领域的一些工具已经在理论计算机科学中得到了应用。我们建议进一步研究这些技术在通信复杂性和性能测试领域的应用。

***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.*****