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

通信复杂性、信息复杂性和属性测试的分析技术

• 批准号: RGPIN-2016-05807
• 负责人: Hatami, Hamed
• 金额: $ 2.77万
• 依托单位: McGill University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=653199
• 关键词: Analytic; techniques; communication; complexity; information

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

***沟通复杂性是理论计算机科学研究中最活跃的研究领域之一。它具有广泛的应用，并采用了其他数学领域的多种技术和工具（例如线性代数，傅立叶分析，差异理论，功能分析，添加剂组合，信息理论等）。除了其在复杂性理论的其他子字段中的应用外，它还通过数据结构和数据流算法具有现实世界的应用。 ***尽管沟通复杂性自出生以来就一直在目睹稳定而快速的进步，但直到几年前，人们一直对信息理论方法的关注才能使人们对该地区的某些经典问题有了更深入的了解。这诞生了一个称为信息复杂性的复杂性理论的新领域。尽管沟通复杂性与最大程度地减少了两个播放器所需的沟通量，以评估取决于其私人输入的函数，但信息复杂性却与传达的位列表揭示了有关两个玩家的输入的信息量有关。 信息复杂性领域与通信复杂性密切相关。 香农是20世纪最重要的数学论文之一，引入了熵的概念，以捕获随机变量中的信息量，并为数字通信时代设定了基础。香农的设置是通信的最简单设置，其中有一个单向频道，一个玩家希望将其数据传输给另一个玩家。随着允许玩家互动，通信复杂性的一般设置更加复杂。然而，正如该领域的最新结果所证明的那样，与随机变量的信息内容赋予传输成本的渐近性方式相似，功能的信息复杂性提供了有关通信复杂性的有价值的信息。*** ***该提案的主要目标之一是以最佳信息成本研究协议，尤其是在该协议中找到该协议，以便找到该协议可以定义的规范。这很重要，因为目前我们对最佳协议的外观几乎没有了解。 该提案的第二个目标是将信息理论方法扩展到复杂性理论的其他领域，该提案的第三个目标是调查添加剂组合学中最新进步的进一步应用，以在交流复杂性和财产测试领域中进行。近年来，添加剂组合学已经取得了令人兴奋的进步。该领域的一些工具在理论计算机科学中找到了应用程序。我们建议研究这些技术在交流复杂性和财产测试领域的进一步应用。*****