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

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

• 批准号: RGPIN-2016-05807
• 负责人: Hatami, Hamed
• 金额: $ 2.77万
• 依托单位: McGill University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=687062
• 关键词: 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世纪最重要的数学论文之一中，引入了熵的概念来捕获随机变量中的信息量，并为数字通信时代奠定了基础。香农的设置是最简单的通信设置，其中有一个单向通道，一个玩家想要将她的数据传输给另一个玩家。当玩家被允许进行交互时，通信复杂性的一般设置更加复杂。然而，正如这一领域的最新结果所表明的那样，类似于随机变量的信息含量给出传输成本的渐近性的方式，函数的信息复杂度提供了关于通信复杂度的有价值的信息。* 本提案的主要目标之一是研究具有最佳信息成本的协议，特别是找到一种可以正确定义此类协议的范式。这一点很重要，因为目前我们对最佳协议的了解很少。 本提案的第二个目标是将信息论方法扩展到其他领域。 领域的复杂性理论，本建议的第三个目标是进一步研究应用的最新进展，在加法组合通信的复杂性和属性测试领域。近年来，加法组合学取得了令人兴奋的进展。这个领域的一些工具已经在理论计算机科学中得到应用。我们建议进一步研究这些技术在通信复杂性和性能测试领域的应用。