Structural theorems in communication complexity

通信复杂性的结构定理

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

Communication occurs in several forms across the domains of science and technology.  For example, it occurs as interactions between different parts of the human brain, as the transmission of data through the internet, as the exchange of signals between different parts of a microchip, as the exchange of information among a handful of supercomputers. The field of communication complexity provides a rigorous framework for measuring, studying, and understanding communication. It is supported by a rich and deep mathematical theory that employs a surprisingly diverse collection of techniques and tools from other areas of mathematics. This proposal aims to investigate a class of mathematical problems in communication complexity that appear across different fields of computer science and pure mathematics in various disguises. Several seemingly different problems in the fields of communication complexity and machine learning on the one hand, and the purely mathematical fields of abstract harmonic analysis and operator theory, on the other hand, are essentially equivalent. This proposal aims to understand these connections better and devise potential approaches to resolve the fundamental underlying mathematical problems. The problems mentioned above arise from the study of very efficient algorithms in communication complexity. As large data sets become more common in science and technology, it has become increasingly important to understand which problems can be solved super-efficiently. The primary objectives of this proposal arise from the study of this problem in the context of communication complexity: Which communication problems are solvable by protocols that exchange only a few bits of communication? It turns out that the above problem has deep connections to problems in complexity theory, machine learning, harmonic analysis, and operator theory. Communication problems, in the most commonly studied framework, are represented by Boolean matrices. Such matrices also represent binary data. For example, the entries of such a matrix could take true or false values depending on which people show which medical symptoms. Machine learning classification algorithms, which predict the label of a new data point based on a known set of correctly labeled points, often rely on the assumption that it is possible to model the data points and their labels geometrically. The performance and accuracy of many of these algorithms rely on the existence of low-dimensional large-margin representations. The mathematical problems considered in this proposal will help us understand which data sets have such desirable geometric representations.

沟通以多种形式发生在整个科学和技术领域。例如，这是作为人脑的不同部分之间的相互作用，作为通过互联网传输数据，因为微芯片的不同部分之间的信号交换，作为少数超级计算机之间的信息交换。沟通复杂性的领域为衡量，研究和理解沟通提供了严格的框架。它得到了丰富而深厚的数学理论的支持，该理论采用了来自其他数学领域的技术和工具的惊人收集。该建议旨在调查交流复杂性中的一类数学问题，这些数学问题出现在计算机科学的不同领域以及各种伪装中的纯数学领域。一方面，在通信复杂性和机器学习领域中，几个看似不同的问题，另一方面，纯粹的数学领域和操作者理论的纯粹数学领域本质上是等效的。该建议旨在更好地理解这些联系，并设计潜在的方法来解决基本的基本数学问题。上述问题来自对通信复杂性非常有效算法的研究。随着大型数据集在科学和技术中变得越来越普遍，了解哪些问题可以高效地解决哪些问题变得越来越重要。该提案的主要目的是由在沟通复杂性的背景下对该问题的研究产生的：通过仅交换几个交流的协议可以解决哪些交流问题？事实证明，上述问题与复杂性理论，机器学习，谐波分析和操作者理论的问题有着深厚的联系。在最常见的框架中，沟通问题由布尔物质代表。此类物品也代表二进制数据。例如，此类矩阵的条目可能会根据人们显示哪些医学症状来采用真或错误的值。基于已知的一组正确标记的点的新数据点的标签预测了机器学习分类算法，通常依赖于以下假设：可以对数据点及其标签进行几何形式建模。这些算法中许多的性能和准确性都取决于低维大幅度表示形式的存在。此提案中考虑的数学问题将有助于我们了解哪些数据集具有如此理想的几何表示。