Structural theorems in 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.